Priority Queues Part II: Implementation

Photo by Sarah Brown on Unsplash

Posted at: http://www.magdysul.com/blog/dockerizing-your-django-application/

In the previous part, we talked about the theory and motivation for priority queues. In this part, we dive a little bit into the implementation.

Priority Queues Part I: What Are They?

Implementation

A priority queue is a data type that supports these operations:

• insert: insert a new key into the queue
• deleteMinimum (or maximum, we’ll get to that): pop and return the minimum (maximum) key from the queue.
• isEmpty: is the collection empty?

These 3 operations would form our main API for the data type. We can go about implementing such a data type in number of ways and we’ll have different implementations of insert and removing max operations depending on how we will structure our priority queue:

1. Array-based (unordered): our “lazy” approach
   - insert: similar to stack’s push, we insert an element at the end of the unordered array, increase the pointer to the end of the array, N. This gives us an O(1) insert.
   - removing max: we linearly search for the max, as in selection sort, and when we find the max, we exchange it with the element at the end of the array and we decrement the pointer to the end of the array (we fake-remove it.) We now have O(n) deleteMaximum
2. Array-based (ordered):
   - insert: Like in insertion sort, find the correct index to insert the key, shift the remaining elements of the array. We have now an O(n) insertion.
   - removing max: the array is already sorted; we remove the last element by decreasing the pointer to the array and returning they key. We get O(1) deleteMaximum.

All elementary implementations leaves us in a position where we have a trade-off between the performances of insert and deleteMaximum operations. But we can get to a third implementation that could guarantee much better performance than O(n) on both operations.

Heap

Heap implementation of a priority queue gives us a fast insert and a fast deleteMaximum. A heap is a data structure in which keys are stored such that each key has value that is bigger than or equal to other two keys at other specific positions.

A heap is a balanced heap-ordered binary tree

If we thought of a heap as a binary tree, each root contains a key that is bigger than the keys in its children. Equivalently, the key in each node is smaller than or equal to the key in that node’s parent (if it has). As we move up from any node, we get a nondecreasing sequence of keys; as we move down, we get a nonincreasing sequence of keys. We can move up and down the tree (or heap) in logarithmic time.

The height of a heap of size N is log N

Heap representation

It’s most convenient to represent a heap as an array. Since a heap is a complete binary tree, we have a good opportunity to use a compact array representation as we don’t need explicit links.

We can see that each node at position k has its parent at position k/2. Similarly, its children are at positions 2k and 2k+1.

This allows us to traverse the heap as we move up from a[k] by continuously going to the nodes parent, k/2. Or move down to 2k and 2k+1

Next part

In the next part, we will take a look at the algorithms that are performed on the heaps and we will be solving a coding challenge that we will try to use priority queues in.

Priority Queues part III: Implementation and Algorithms - Magdy's

References

• Algorithms, 4th ed.
• Wikipedia articles on Huffman Coding, Dijkstra’s algorithm, Priority Queue