python tutorial - Python - data structure priority queue and heapq - learn python - python programming
Priority Queue
- 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.
try:
import Queue as Q # ver. < 3.0
except ImportError:
import queue as Q
q = Q.PriorityQueue()
q.put(10)
q.put(1)
q.put(5)
while not q.empty():
print q.get(),click below button to copy the code. By Python tutorial team
Output:
1 5 10 - 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:
try:
import Queue as Q # ver. < 3.0
except ImportError:
import queue as Q
q = Q.PriorityQueue()
q.put((10,'ten'))
q.put((1,'one'))
q.put((5,'five'))
while not q.empty():
print q.get(),click below button to copy the code. By Python tutorial team
Output:
(1, 'one') (5, 'five') (10, 'ten')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:
try:
import Queue as Q # ver. < 3.0
except ImportError:
import queue as Q
class Skill(object):
def __init__(self, priority, description):
self.priority = priority
self.description = description
print 'New Level:', description
return
def __cmp__(self, other):
return cmp(self.priority, other.priority)
q = Q.PriorityQueue()
q.put(Skill(5, 'Proficient'))
q.put(Skill(10, 'Expert'))
q.put(Skill(1, 'Novice'))
while not q.empty():
next_level = q.get()
print 'Processing level:', next_level.descriptionclick below button to copy the code. By Python tutorial team
Output:
New Level: Proficient
New Level: Expert
New Level: Novice
Processing level: Novice
Processing level: Proficient
Processing level: Expertheapq - Heap queue
- The heapq implements a min-heap sort algorithm suitable for use with Python's lists.
import heapq
heap = []
heapq.heappush(heap, (1, 'one'))
heapq.heappush(heap, (10, 'ten'))
heapq.heappush(heap, (5,'five'))
for x in heap:
print x,
print
heapq.heappop(heap)
for x in heap:
print x,
print
# the smallest
print heap[0]click below button to copy the code. By Python tutorial team
Output
(1, 'one') (10, 'ten') (5, 'five')
(5, 'five') (10, 'ten')
(5, 'five')heapq - heapify
- We can Transform list $x$ into a heap, in-place, in linear time:
Sample Code
heapq.heapify(x)click below button to copy the code. By Python tutorial team
Example
import heapq
heap = [(1, 'one'), (10, 'ten'), (5,'five')]
heapq.heapify(heap)
for x in heap:
print x,
print
heap[1] = (9, 'nine')
for x in heap:
print x,click below button to copy the code. By Python tutorial team
Output:
(1, 'one') (10, 'ten') (5, 'five')
(1, 'one') (9, 'nine') (5, 'five')Note that we replaced (10, 'ten') with (9, 'nine').