Carl Nolan’s ramblings on development
I thought I would take a break for a while from Hadoop and put together an F# .Net implementation of a Priority Queue; implemented using a heap data structure. Conceptually we can think of a heap as a balanced binary tree. The tree will have a root, and each node can have up to two children; a left and a right child. The keys in such a binary tree are said to be in heap order, such that any element is at least as large as its parent element.
For every element v, at a node i, the element w at i’s parent satisfies key(w)≤key(v)
The heap is maintained as an array, indexed by i=1…N, such that for any node i, the nodes at positions leftChild(i)=2i and rightChild(i)=2i+1, and the parent of the node is at position parent(i)=(1/2).
The idea behind a Priority Queue is that finding the element with the lowest key is easy, O(1) time, as it is always the root. When adding a new element it is always added to the end of the list. The heap is then fixed by recursively checking the new element with its parent, and swapping their positions in the list until the heap condition is satisfied. This operation takes O(log n) time.
Within .Net we implemented a Priority Queue using a List<KeyValuePair<'TKey, 'TValue>>.
The code, as always can be downloaded from:
The basic operations supported on the Priority Queue will be:
Before showing the code a quick word is warranted about the implementation. The Key operations shown above rely on a second data structure; a Dictionary<'TKey, int>. This secondary data structure maintains a reference of the index within the list for each key. This positional structure uses a list off index values associated with each key, allowing items with the same key value to be added to the queue.
So what does the F# code look like:
This code implementation has the PriorityQueue derive from ICollection. The implementation is analogous to the .Net Queue implementation, but with Key and Value pairs; but more importantly where Dequeue is guaranteed to return the element with the lowest value.
The correctness of the heap is managed through the heapify operations. It is these recursive operations that compare parent and child nodes and adjust the positions accordingly.
One has to remember though that the enumerator will effectively return elements in a random order.