Data Structure - Priority Queue & heapq

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.

from wiki Priority queue.

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(),

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.

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(),

Output:

(1, 'one') (5, 'five') (10, 'ten')

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.description

Output:

New Level: Proficient
New Level: Expert
New Level: Novice
Processing level: Novice
Processing level: Proficient
Processing level: Expert

The heapq implements a min-heap sort algorithm suitable for use with Python's lists.

This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.

Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which $heap\left[k\right] \le heap\left[2*k+1\right]$ and $heap\left[k\right] \le heap\left[2*k+2\right]$ for all $k$, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root, $heap\left[0\right]$.

From https://docs.python.org/2/library/heapq.html.

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]

Output:

(1, 'one') (10, 'ten') (5, 'five')
(5, 'five') (10, 'ten')
(5, 'five')

We can Transform list $x$ into a heap, in-place, in linear time:

heapq.heapify(x)

For 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,

Output:

(1, 'one') (10, 'ten') (5, 'five')
(1, 'one') (9, 'nine') (5, 'five')

Note that we replaced (10, 'ten') with (9, 'nine').