## 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]$.

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').

Ph.D. / Golden Gate Ave, San Francisco / Seoul National Univ / Carnegie Mellon / UC Berkeley / DevOps / Deep Learning / Visualization