pythonic-data-structures 0.2.1

抽象和树状数据结构-python

存储库包含流行数据结构的基于python的实现。

安装：

请使用"pip install pythonic data structures"。

问题：

请注册您在github存储库中发现的任何问题，以便尽快解决它们。

要求：

不依赖于外部库。但是，需要python 3.x版本。

文件：

导航到数据结构：堆栈，队列，最小二进制堆， 最大二进制堆，优先级队列，重复优先级队列，图

数据结构

在python中实现堆栈、队列、最大二进制堆、最小二进制堆、优先级队列和图形 它们位于abstractdatastructures.py和treedatastructures.py模块中

• 堆栈（先进先出）
  堆栈的实现环绕python deque对象，但也是通用的：您可以指定元素的类型 在构造器的堆栈中。如果未指定，则将其设置为"无"，并且可以将任何类型的元素添加到堆栈中。这个 实现包括堆栈的所有常见操作：peek、push、pop、size等。
  

API：

fromDataStructures.AbstractDataStructuresimportStack# import the stack data structurestack=Stack()# type is set to None, items of any types can be addedstack=Stack(elements_type=int)# type is set to int, hence only integers can be pushedstack.size# the number of elements in the stacklen(stack)# same as stack.sizestr(stack)# returns the string representation of the python deque object containing the elements of the stackitem="test_item"stack.contains(item)# returns True if the item is in the stack and False otherwise# contains raises a StackTypeError if the type of the stack is not None and is different than the type of the parameterboolean=iteminstack# same as boolean = stack.contains(item)stack.type# returns the type of the elements in the stack, None if no type is specified when initialisedstack.peek()# returns the last element that was added to the stack, but doesn't remove it# peek returns None if there are no elements in the stackstack.pop()# same as peek(), but removes the last element that was added to the stack# pop raises an EmptyStackError if there are no elements in the stackelement="test_item"stack.push(element)# pushes the element to the top of the stack# push raises a StackTypeError if the stack has a specified type for elements and the argument is not of that type# the implementation includes an iteratorforelementinstack:print(element)# keep in mind that the iterator uses stack.pop() to get the next element, hence# after the iteration is over the stack would be emptystack.remove(element)# removes the element from the stack# raises a StackTypeError if the stack has a specified type for elements and the argument is not of that type# raises a StackElementError if the stack doesn't contain the element specified as argument

• 队列（先进先出）
  队列的实现环绕python deque对象，但也是通用的：您可以在构造函数中指定队列中元素的类型。 如果未指定，则将其设置为none，并且可以将任何类型的元素添加到队列中。这个 实现包括队列的所有常见操作：排队、出列、查看、大小等。
  

API：

fromDataStructures.AbstractDataStructuresimportQueue# import the queue data structurequeue=Queue()# type is set to None, items of any types can be addedqueue=Queue(elements_type=str)# type is set to str, hence only strings can be enqueuedqueue.size# the number of elements in the queuelen(queue)# same as queue.sizestr(queue)# returns the string representation of the python deque object containing the elements of the queueitem="test_item"queue.contains(item)# returns True if the item is in the queue and False otherwise# contains raises a QueueTypeError if the type of the queue is not None and is different # than the type of the parameterboolean=iteminqueue# same as boolean = queue.contains(item)queue.type# the type of the elements in the queue, None if no type is specified when initialisedqueue.peek()# returns the first element that was added to the queue, but doesn't remove it# peek returns None if there are no elements in the queuequeue.dequeue()# same as peek(), but removes the first element that was added to the queue# dequeue raises a EmptyQueueError if there are no elements in the queueelement="test_element"queue.enqueue(element)# enqueues the element to the back of the queue# enqueue raises a QueueTypeError if the queue has a specified type for elements# and the argument is not of that type# the implementation includes an iteratorforelementinqueue:print(element)# keep in mind that the iterator uses queue.dequeue() to get the next element, hence# after the iteration is over the queue would be emptyqueue.remove(element)# removes the element from the queue# raises a QueueTypeError if the queue has a specified type for elements and the argument is not of that type# raises a QueueElementError if the queue doesn't contain the element specified as argument

• 二进制堆 BinaryHeap的实现是通用的：可以在构造函数中指定堆中元素的类型。如果没有 指定时，它被设置为int，因此只能将整数添加到堆中。BinaryHeap类是抽象的。你不能 实例化它。该实现包括两种类型的堆，您可以使用它们：minbinaryheap和maxbinaryheap。

fromDataStructures.AbstractDataStructuresimportMinBinaryHeap# import the min heapmin_heap=MinBinaryHeap()# type is set to default - int, hence only integers can be added# creates an empty heapmin_heap=MinBinaryHeap(str)# type is set to str, hence only strings can be added# creates an empty heapmin_heap.size# the number of elements in the heaplen(min_heap)# same as min_heap.sizestr(min_heap)# returns a string of the list of elements in the heapmin_heap.type# the type of elements in the heapelement="test_element"min_heap.add(element)# adds the element to the min binary heap on the place it should be located# add raises a BinaryHeapTypeError if the type of the argument is not the same as the type of the elements in the heapmin_heap.peek_min()# returns the minimum element (the root), but doesn't remove it from the heap# returns None if heap is emptymin_heap.remove_min()# returns the minimum element (the root) and removes it from the heap# the method replaces the root with the second minimum element in the heap# it raises a EmptyBinaryHeapError if the heap is empty# returns the minimum element (the root) and removes it from the heap, by replacing it with the element argumentmin_heap.replace_root(element)# same as min_heap.remove_min() followed by min_heap.add(element), but replace_root() is faster# raises a BinaryHeapTypeError if the type of the argument is not the same as the type of the elements in the heap# raises a EmptyBinaryHeapError if the heap is emptymin_heap.get_sorted_elements()# returns a list with the sorted elements from the heap, the heap remains unchanged# the order is ascending; returns an empty list if the heap is empty# the iterator goes through each element in the heap in ascending orderforelementinmin_heap:print(element)# keep in mind that using the iterator will remove each element you go through from the heap, since it uses remove_min()# to generate the next element, hence when the iterator is finished the heap would be empty;# if you want to keep the elements in the heap, use get_sorted_elements() (although it's slightly slower)# another example with the iteratorheap_iter=iter(min_heap)whileTrue:try:print(next(heap_iter))exceptStopIteration:breakmin_heap.size# will return 0 after iteration is finished, as explained aboveold_element,new_element=10,100min_heap.replace(old_element,new_element)# replaces the old element with the new element and readjusts the heap after# the replacement# raises a BinaryHeapTypeError if the type of the first or the second argument is not the same as the type of the # elements in the heap# raises a BinaryHeapElementError if the old_element argument is not contained in the heap# raises a EmptyBinaryHeapError if the heap is emptymin_heap.remove(element)# removes the element and readjusts the heap after deletion# raises a BinaryHeapTypeError if the type of the argument is not the same as the type of the elements in the heap# raises a BinaryHeapElementError if the element argument is not contained in the heap# raises a EmptyBinaryHeapError if the heap is empty

fromDataStructures.AbstractDataStructuresimportMaxBinaryHeap# import the max heapmax_heap=MaxBinaryHeap()# type is set to default - int, hence only integers can be added# creates an empty heapmax_heap=MaxBinaryHeap(str)# type is set to str, hence only strings can be added# creates an empty heapmax_heap.size# the number of elements in the heaplen(max_heap)# same as max_heap.sizestr(max_heap)# returns a string of the list of elements in the heapmax_heap.type# the type of elements in the heapelement="test_element"max_heap.add(element)# adds the element to the max binary heap on the place it should be located# add raises a BinaryHeapTypeError if the type of the argument is not the same as the type of the elements in the heapmax_heap.peek_max()# returns the maximum element (the root), but doesn't remove it from the heap# returns None if heap is emptymax_heap.remove_max()# returns the maximum element (the root) and removes it from the heap# the method replaces the root with the second maximum element in the heap# it raises a EmptyBinaryHeapError if the heap is empty# returns the maximum element (the root) and removes it from the heap, by replacing it with the element argumentmax_heap.replace_root(element)# same as max_heap.remove_max() followed by max_heap.add(element), but replace_root() is faster# raises a BinaryHeapTypeError if the type of the argument is not the same as the type of the elements in the heap# raises a EmptyBinaryHeapError if the heap is emptymax_heap.get_sorted_elements()# returns a list with the sorted elements from the heap, the heap remains unchanged# the order is descending; returns an empty list if the heap is empty# the iterator goes through each element in the heap in descending orderforelementinmax_heap:print(element)# keep in mind that using the iterator will remove each element you go through from the heap, since it uses remove_max()# to generate the next element, hence when the iterator is finished the heap would be empty;# if you want to keep the elements in the heap, use get_sorted_elements() (although it's slightly slower)# another example with the iteratorheap_iter=iter(max_heap)whileTrue:try:print(next(heap_iter))exceptStopIteration:breakmax_heap.size# will return 0 after iteration is finished, as explained aboveold_element,new_element=10,100max_heap.replace(old_element,new_element)# replaces the old element with the new element and readjusts the heap after# the replacement# raises a BinaryHeapTypeError if the type of the first or the second argument is not the same as the type of the # elements in the heap# raises a BinaryHeapElementError if the old_element argument is not contained in the heap# raises a EmptyBinaryHeapError if the heap is emptymax_heap.remove(element)# removes the element and readjusts the heap after deletion# raises a BinaryHeapTypeError if the type of the argument is not the same as the type of the elements in the heap# raises a BinaryHeapElementError if the element argument is not contained in the heap# raises a EmptyBinaryHeapError if the heap is empty

fromDataStructures.AbstractDataStructuresimportPriorityQueue# import the priority queue data structurepriority_queue=PriorityQueue()# type is set to default None, hence objects of all types can be enqueued to the queue# the reverse argument is set to default False, hence dequeue returns the element with the highest prioritypriority_queue=PriorityQueue(elements_type=str,reverse=True)# type is set to str, hence only strings can be enqueued# the reverse argument is set to True, hence dequeue returns the element with the lowest prioritypriority_queue.size# the number of elements in the queuelen(priority_queue)# same as priority_queue.sizestr(priority_queue)# returns a string of the dictionary linking priorities with elements in the queuepriority_queue.type# the type of elements that can be enqueued in the priority queue# if this method returns None, objects of all types can be enqueuedpriority_queue.reversed# True if the queue dequeues the element with the lowest priority# returns False if the queue dequeues the element with the highest prioritypriority=10priority_queue.contains_priority(priority)# returns True if the queue has an element linked to the given priority and False otherwise# contains raises a PriorityQueueTypeError if type of priority is not intelement="test_element"priority_queue.contains_element(element)# returns True if an element is contained in the queue# raises PriorityQueueTypeError if priority_queue.type is not None and is different than the type of the given elementboolean=elementinpriority_queue# same as priority_queue.contains_element(element)item="test_item"priority_queue.enqueue(item,priority)# enqueues the given item and links it the given priority# raises PriorityQueueTypeError if type(priority) is not int# raises PriorityQueueTypeError if priority_queue.type is not None and is different than the type of the given item# keep in mind that if there is another element linked to the same priority, the old element will be replaced# by the new elementpriority_queue.enqueue("first_item",5)priority_queue.enqueue("second_item",5)# doing this will link priority 5 to str object "second_item" while str object "first_item" will be ignored and # removed from the queue# Another thing to note is that you can enqueue the same element to different prioritiespriority_queue.enqueue("item",10)priority_queue.enqueue("item",11)priority_queue.peek()# returns element with minimum or maximum priority in the queue, but doesn't remove it from the queue# if priority_queue.reversed is False, it returns the element with the maximum priority# if priority_queue.reversed is True, it returns the element with the minimum priority# returns None if the queue is emptypriority_queue.dequeue()# same as priority_queue.peek(), but removes the returned element from the queue# raises a EmptyPriorityQueueError if the queue is empty priority_queue.get_element(priority)# returns the element linked to the given priority# returns None if no element is linked to this priority# raises a PriorityQueueTypeError if type(priority) is not int# the implementation includes an iterator tooforiteminpriority_queue:print(item)# keep in mind that the iterator uses priority_queue.dequeue() to get the next element, hence after the iteration # is finished the priority_queue will be emptypriority_queue.replace_priority(element,priority)# replaces the given element's priority with the new priority argument# returns a boolean representing whether the element's priority has been replaced# raises PriorityQueueTypeError if type(priority) is not int# raises PriorityQueueTypeError if priority_queue.type is not None and is different than the type of the given element# raises PriorityQueueElementError if the element is not contained in the queue# if there is another element already assigned to the new priority, the old element will be replaced with the element # given as argument, thus the old element will be ignored and removed# you can also pass a third argument to the replace_priority method - comparisoncomparison_type=1priority_queue.replace_priority(element,priority,comparison=comparison_type)# returns a boolean representing whether the element's priority has been replaced# by doing so the priority of the element will only be replaced if a certain type of comparison between # the two priorities holds# if comparison is 1, the priorities will be replaced if the new priority is greater than the old priority# if comparison is -1, the priorities will be replaced if the new priority is less than the old priority# if comparison is None (default), the priorities will always be replaced# raises ValueError if comparison is not -1, 1 or Nonepriority_queue.remove_element(element)# finds and removes the element from the queue# raises PriorityQueueTypeError if priority_queue.type is not None and is different than the type of the given element# raises PriorityQueueElementError if the queue doesn't contain the element

fromDataStructures.AbstractDataStructuresimportDuplicatePriorityQueue# import the priority queue data structurequeue=DuplicatePriorityQueue()# type is set to default None, hence objects of all types can be enqueued to the queue# the reverse argument is set to default False, hence dequeue returns the element with the highest priorityqueue=DuplicatePriorityQueue(elements_type=str,reverse=True)# type is set to str, hence only strings can be enqueued# the reverse argument is set to True, hence dequeue returns the element with the lowest priorityqueue.size# the number of elements in the queue, # elements with the same priority are NOT counted as one element, but as ordinary elementslen(queue)# same as queue.sizestr(queue)# returns a string of the dictionary linking priorities with elements in the queue# keep in mind that if there is a priority linked to more than one element, the string representation will return# the priority linked to a Queue objectqueue.type# the type of elements that can be enqueued in the priority queue# if this method returns None, objects of all types can be enqueuedqueue.reversed# returns True if the queue dequeues the element with the lowest priority# returns False if the queue dequeues the element with the highest prioritypriority=10queue.contains_priority(priority)# returns True if the queue has an element or elements linked to the given priority and False otherwise# contains raises a PriorityQueueTypeError if type of priority is not intelement="test_element"queue.contains_element(element)# returns True if an element is contained in the queue# raises PriorityQueueTypeError if queue.type is not None and is different than the type of the given elementboolean=elementinqueue# same as queue.contains_element(element)item="test_item"queue.enqueue(item,priority)# enqueues the given item and links it the given priority# raises PriorityQueueTypeError if type(priority) is not int# raises PriorityQueueTypeError if priority_queue.type is not None and is different than the type of the given item# in this implementation of a priority queue, if there is already an item with the given priority in the queue, then both # items will be retained and when dequeueing they will be dequeued in the order they were enqueuedqueue.enqueue("first_item",5)queue.enqueue("second_item",5)queue.dequeue()# dequeues "first_item"queue.dequeue()# dequeues "second_item"# Another thing to note is that you can enqueue the same element to different prioritiesqueue.enqueue("item",10)queue.enqueue("item",11)queue.peek()# returns element with minimum or maximum priority in the queue, but doesn't remove it from the queue# if priority_queue.reversed is False, it returns the element with the maximum priority# if priority_queue.reversed is True, it returns the element with the minimum priority# returns None if the queue is empty# if there are more than one elements with the same priority, peek() will return the first element that was enqueuedqueue.dequeue()# same as priority_queue.peek(), but removes the returned element from the queue# raises a EmptyPriorityQueueError if the queue is empty # if there are more than one elements with the same priority, dequeue() will return and remove them in the order they were# enqueuedqueue.get_element(priority)# returns the element linked to the given priority# returns None if no element is linked to this priority# raises a PriorityQueueTypeError if type(priority) is not int# if there are more than one elements with the same priority, get() will return the first element that was enqueued# the implementation includes an iterator tooforiteminqueue:print(item)# keep in mind that the iterator uses priority_queue.dequeue() to get the next element, hence after the iteration # is finished the queue will be emptyqueue.replace_priority(element,priority)# replaces the given element's priority with the new priority argument# raises PriorityQueueTypeError if type(priority) is not int# raises PriorityQueueTypeError if queue.type is not None and is different than the type of the given element# raises PriorityQueueElementError if the element is not contained in the queue# in this implementation duplicated priorities are allowed, hence no elements will be ignored even if there is already# an element assigned to the new priority# you can also pass a third argument to the replace_priority method - comparisoncomparison_type=1queue.replace_priority(element,priority,comparison=comparison_type)# by doing so the priority of the element will only be replaced if a certain type of comparison between # the two priorities holds# if comparison is 1, the priorities will be replaced if the new priority is greater than the old priority# if comparison is -1, the priorities will be replaced if the new priority is less than the old priority# if comparison is None (default), the priorities will always be replaced# raises ValueError if comparison is not -1, 1 or Nonequeue.remove_element(element)# finds and removes the element from the queue# raises PriorityQueueTypeError if queue.type is not None and is different than the type of the given element# raises PriorityQueueElementError if the queue doesn't contain the element

nodes=[5.5,"word",100]

edges=[[None,None,1,None,None],[None,None,None,None,None],[1,None,None,None,None],[None,None,None,None,None],[None,None,None,None,None]]

fromDataStructures.AbstractDataStructuresimportGraph# import the graph data structuregraph=Graph()# initialize a graph with None elements type, hence all types of elements can be added to the graph# the initialized graph is also neither directed, nor oriented, nor weightedgraph=Graph(elements_type=int,directed=True,oriented=False,weighted=True)# only integers can be added to the initialized graph; the graph is directed, but not oriented; the graph is also weightedgraph=Graph(elements_type=str,directed=False,oriented=True,weighted=True)# this raises an InvalidGraphError since a graph cannot be oriented and not directed at the same timegraph=Graph(float,True,True,True)# only floats can be added to the initialized graph; the graph is directed, oriented and weightedgraph.size# the number of elements in the graphlen(graph)# same as graph.sizestr(graph)# returns a string in the format 'Graph: directed - boolean, oriented - boolean, weighted - boolean'graph.type# the type of node values in the graph, returns None if all types of elements are allowed# if this method doesn't return None, only nodes of the returned type can be added to the graphgraph.directed# True if the graph is directed and False otherwisegraph.oriented# True if the graph is oriented and False otherwisegraph.weighted# True if the graph is weighted and False otherwiseitem="test_element"graph.contains(item)# returns True if item is in the set of nodes of the graph and False otherwise# raises a GraphTypeError if the type of the graph is not None and is different than the type of the argumentboolean=itemingraph# same as graph.contains(item)first_item="first_test_item"second_item="second_test_item"graph.contains_edge(first_item,second_item)# returns True if an edge from first_item to second_item exists# raises a GraphTypeError if the type of the graph is not None and is different than the type of any of the arguments# raises a GraphElementError if first_item or second_item is not a node that the graph contains# if the graph is not directed the result will be the same even if you reverse the order of the argumentsgraph.get_edge_weight(first_item,second_item)# raises a GraphTypeError if the type of the graph is not None and is different than the type of any of the arguments# raises a GraphElementError if first_item or second_item is not a node that the graph contains# raises a GraphEdgeError if the graph is not weighted# raises a GraphEdgeError if an edge between first_item and second_item doesn't exist# if the graph is not directed the result will be the same even if you reverse the order of the argumentsgraph.nodes()# returns a deep copy of the list of nodes of the graph# a deep copy is returned to avoid manual changes of the graph by changing the elements in the returned listgraph.add_node(item)# adds item to the nodes of the graph if it is not already added# raises a GraphTypeError if the type of the graph is not None and is different than the type of the argument# raises an GraphElementError if item is None# if item is already added as a node to the graph, the function does nothinggraph.remove_node(item)# raises a GraphTypeError if the type of the graph is not None and is different than the type of the argument# raises a GraphElementError if item is not a node in the graph# remove a node in the graph also removes all edges related to this node (going to and from this node)old_node="test_old_node"new_node="test_new_node"graph.replace_node(old_node,new_node)# replaces old_node with new_node in the graph list of nodes if possible# raises a GraphTypeError if the type of the graph is not None and is different than the type of any of the arguments# raises a GraphElementError if old_node is not a node the graph contains# raises a GraphElementError if new_node is a node the graph contains, since duplicate nodes are not allowed# the replacing of a node in the graph doesn't affect the edges in the graph, e.g.connected_nodes=graph.edges_of(old_node)graph.replace_node(old_node,new_node)new_connected_nodes=graph.edges_of(new_node)print(connected_nodes==new_connected_nodes)# will print True, since edges of the old node are not affected, only the value is replaced# the method is useful, since it retains the edges of the old node # and is faster than first removing the old node and then adding the new nodegraph.edges()# returns a deep copy of the square matrix (2D list) representing the edges of the graph# a deep copy is returned to avoid manual changes of the graph by changing the elements in the returned listgraph.edges_of(item)# returns a list of all nodes to which there is an edge from the argument# returns an empty list if there are no such nodes# raises a GraphTypeError if the type of the graph is not None and is different than the type of the argument# raises a GraphElementError if the item if not a node in the graphedge_weight="test_edge_weight"graph.add_edge(first_item,second_item,edge_weight)# adds an edge from first_item to second_item with the given edge_weight if appropriate# edge_weight should only be specified if the graph is weighted, otherwise, just skip this argument (set to None by default)# raises a GraphTypeError if the type of the graph is not None and is different than the type of any of the arguments# raises a GraphTypeError if edge_weight is specified and is not of type float or int# raises a GraphElementError if first_item or second_item is not a node that the graph contains# raises a GraphEdgeError if the graph is weighted and edge_weight is not specified or it is None# raises a GraphEdgeError if the graph is oriented and an edge from second_item to first_item already existsgraph.remove_edge(first_item,second_item)# removes the edge from first_item to second_item# if the graph is not directed, this function removes the edge from second_item to first_item too# raises a GraphTypeError if the type of the graph is not None and is different than the type of any of the arguments# raises a GraphElementError if first_item or second_item is not a node that the graph contains# raises a GraphEdgeError if there is no edge from first_item to second_item# the implementation includes an iterator toofornodeingraph:print(node)# the iterator goes through all nodes in the graph# the __iter__ method actually returns the iterator of the list of nodes of the graph