python tutorial - Python - data structure priority queue and heapq - learn python - python programming
- A priority queue is an abstract data type (ADT) which is like a regular queue or stack data structure, but where additionally each element has a priority associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.
- While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like a list or a map; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
Sample A - simplest
- The following code the most simplest usage of the priority queue.
- As we can see from the output, the queue stores the elements by priority not by the order of element creation. Note that depending on the Python versions, the name of the priority queue is different. So, we used try and except pair so that we can adjust our container to the version.
- The priority queue not only stores the built-in primitives but also any objects as shown in next section.
Sample B - tuple
- The priority queue can store objects such as tuples:
Sample C - class objects using __cmp__()
- Python isn't strongly typed, so we can save anything we like: just as we stored a tuple of (priority,thing) in previous section. We can also store class objects if we override __cmp__() method:
heapq - Heap queue
- The heapq implements a min-heap sort algorithm suitable for use with Python's lists.
heapq - heapify
- We can Transform list $x$ into a heap, in-place, in linear time:
Note that we replaced (10, 'ten') with (9, 'nine').