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. We will see possible implementations of a priority queue, especially heap implementation, and in the next part of the series we will have a look at the Java 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:
- 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
- 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.
Priority Queues Heap Implementation
Heap implementation of a priority queue gives us a fast insert and a fast deleteMaximum. Let’s dig deeper into priority queues heap implementation. 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
In the previous paragraphs, we learned that 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
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.
- Algorithms, 4th ed.
- Wikipedia articles on Huffman Coding, Dijkstra’s algorithm, Priority Queue.