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:

http://code.msdn.microsoft.com/Net-Implementation-of-a-d3ac7b9d

The basic operations supported on the Priority Queue will be:

Enqueue Adds an item to the Queue
Dequeue Removes the root element; that with the lowest key
Peek Queries the root element
IndexOf Returns the index of a given key value pair
RemoveAt Removes the element at the specified index value
ContainsKey Determines whether the Queue contains a specific key value
ChangeKey Changes a specific key value
RemoveKey Removes the element with the specific key value
Item An indexer based on the key value

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 does restrict the Priority Queue to unique key values, but does provide greater flexibility for the heap operations; all in O(1) time.

So what does the F# code look like:

  1. namespace MSDN.FSharp
  2.  
  3. open System
  4. open System.Collections
  5. open System.Collections.Generic
  6.  
  7. type PriorityQueue<'TKey, 'TValue when 'TKey : comparison> private (data:IEnumerable<KeyValuePair<'TKey, 'TValue>> option, capacity:int, comparer:IComparer<'TKey>) =   
  8.  
  9.     let mutable heapList:List<KeyValuePair<'TKey, 'TValue>> =  null
  10.     let mutable positionDict:Dictionary<'TKey, int> = null
  11.  
  12.     // Determines if a value is in the heap
  13.     let inRange index =
  14.         if index >= 0 && index < heapList.Count then Some(index) else None
  15.     let checkIndex index =
  16.         if ((inRange index).IsNone) then raise (ArgumentException(sprintf "Index specified is not within range - %i" index))
  17.  
  18.     // Gets the children of a node
  19.     let getChildren (index:int) =
  20.         // children left[2*pos] and right[2*pos + 1] where pos = index + 1
  21.         let left = (2 * index) + 1
  22.         let right = (2 * index) + 2     
  23.         (inRange left, inRange right)
  24.  
  25.     // Gets the parent of an index
  26.     let getParent (index:int) =
  27.         // parent index [pos/2] where index = pos - 1
  28.         if (index = 0) then None
  29.         else Some((index-1) / 2)
  30.  
  31.     // Tests to see if the first value is greater than the first
  32.     let isGreater parent child =
  33.         if (comparer.Compare(heapList.[parent].Key, heapList.[child].Key) > 0) then true
  34.         else false
  35.             
  36.     // Swaps two elements of the heap list
  37.     let swapElements idx1 idx2 =
  38.         let element1 = heapList.[idx1]
  39.         let element2 = heapList.[idx2]
  40.         heapList.[idx1] <- heapList.[idx2]
  41.         heapList.[idx2] <- element1
  42.         positionDict.[element1.Key] <- idx2
  43.         positionDict.[element2.Key] <- idx1
  44.  
  45.     // Heapifys toward the parent
  46.     let rec heapifyUp (index:int) =
  47.         if (index > 0) then
  48.             let parent = getParent index
  49.             if (isGreater parent.Value index) then
  50.                 swapElements parent.Value index
  51.                 heapifyUp parent.Value
  52.  
  53.     // Heapifys down to the children
  54.     let rec heapifyDown (index:int) =
  55.         let (left, right) = getChildren index
  56.         if (left.IsSome) then
  57.             let childindex =
  58.                 if (right.IsSome && (isGreater left.Value right.Value)) then right.Value
  59.                 else left.Value
  60.             if (isGreater index childindex) then
  61.                 swapElements index childindex
  62.                 heapifyDown childindex
  63.  
  64.     // Heapifys down to the children
  65.     let heapifyUpDown (index:int) =
  66.         let parent =  getParent index
  67.         if (parent.IsSome && (isGreater parent.Value index)) then
  68.             heapifyUp index
  69.         else
  70.             heapifyDown index
  71.  
  72.     // Adds an items and heapifys
  73.     let insertItem (key:'TKey) (value:'TValue) =
  74.         let insertindex = heapList.Count
  75.         positionDict.Add(key, insertindex)
  76.         heapList.Add(new KeyValuePair<'TKey, 'TValue>(key, value))
  77.         heapifyUp(insertindex)
  78.  
  79.     // Delete the root node and heapifys
  80.     let deleteItem index =
  81.         if (heapList.Count <= 1) then
  82.             heapList.Clear()
  83.             positionDict.Clear()
  84.         else
  85.             let lastindex = heapList.Count - 1
  86.             let indexKey =  heapList.[index].Key
  87.             let lastKey = heapList.[lastindex].Key
  88.             heapList.[index] <- heapList.[lastindex]
  89.             positionDict.[lastKey] <- index
  90.             heapList.RemoveAt(lastindex)
  91.             positionDict.Remove(indexKey) |> ignore
  92.             heapifyDown index
  93.  
  94.     // Default do bindings
  95.     do
  96.         if (comparer = null) then
  97.             raise (ArgumentException("Comparer cannot be null"))
  98.  
  99.         let equalityComparer =
  100.             { new IEqualityComparer<'TKey> with
  101.                 override x.Equals(c1, c2) =
  102.                     if ((comparer.Compare(c1, c2)) = 0) then true
  103.                     else false
  104.                 override x.GetHashCode(value) =
  105.                     value.GetHashCode()
  106.             }
  107.  
  108. ��       heapList <- new List<KeyValuePair<'TKey, 'TValue>>(capacity)
  109.         positionDict <- new Dictionary<'TKey, int>(capacity, equalityComparer)
  110.  
  111.         if data.IsSome then
  112.             data.Value |> Seq.iter (fun item -> insertItem item.Key item.Value)
  113.  
  114.     // Set of constructors
  115.     new() = PriorityQueue(None, 0, ComparisonIdentity.Structural<'TKey>)
  116.     new(capacity:int) = PriorityQueue(None, capacity, ComparisonIdentity.Structural<'TKey>)
  117.     new(data:IEnumerable<KeyValuePair<'TKey, 'TValue>>) = PriorityQueue(Some(data), 0, ComparisonIdentity.Structural<'TKey>)
  118.     new(comparer:IComparer<'TKey>) = PriorityQueue(None, 0, comparer)
  119.     new(capacity:int, comparer:IComparer<'TKey>) = PriorityQueue(None, capacity, comparer)
  120.     new(data:IEnumerable<KeyValuePair<'TKey, 'TValue>>, comparer:IComparer<'TKey>) = PriorityQueue(Some(data), 0, comparer)
  121.  
  122.     // Checks to see if the heap is empty
  123.     member this.IsEmpty
  124.         with get() = (heapList.Count = 0)
  125.  
  126.     // Enqueues a new entry into the heap
  127.     member this.Enqueue (key:'TKey) (value:'TValue) =
  128.         insertItem key value
  129.         ()
  130.  
  131.     // Peeks at the head of the heap
  132.     member this.Peek() =
  133.         if not(this.IsEmpty) then
  134.             heapList.[0]
  135.         else
  136.             raise (InvalidOperationException("Priority Queue is empty"))
  137.  
  138.     // Dequeues the head entry into the heap
  139.     member this.Dequeue() =
  140.         let value = this.Peek()
  141.         deleteItem 0
  142.         value
  143.  
  144.     // Determines whether an item is in the queue
  145.     member this.Contains (key:'TKey) (value:'TValue) =
  146.         heapList.Contains(new KeyValuePair<'TKey, 'TValue>(key, value))
  147.  
  148.     // Returns the index of a specified item
  149.     member this.IndexOf (key:'TKey) (value:'TValue) =
  150.         heapList.IndexOf(new KeyValuePair<'TKey, 'TValue>(key, value))
  151.  
  152.     // Removes an item from the queue at the specified index
  153.     member this.RemoveAt (index:int) =
  154.         checkIndex index
  155.         deleteItem index
  156.  
  157.     // Determines whether an item is in the queue
  158.     member this.ContainsKey (key:'TKey) =
  159.         positionDict.ContainsKey key
  160.  
  161.     // Determines whether an item is in the queue
  162.     member this.ChangeKey (key:'TKey) (value:'TKey)=
  163.         let index = positionDict.[key]
  164.         let item = heapList.[index]
  165.         heapList.[index] <- new KeyValuePair<'TKey, 'TValue>(value, item.Value)
  166.         positionDict.Remove(key) |> ignore
  167.         positionDict.Add(value, index)
  168.         heapifyUpDown index
  169.  
  170.     // Removes an item from the queue for the specified key
  171.     member this.RemoveKey (key:'TKey) =
  172.         let index = positionDict.[key]
  173.         this.RemoveAt index
  174.  
  175.     // Modifies elements based on index values
  176.     member this.Item
  177.         with get(key) =
  178.             let index = positionDict.[key]
  179.             heapList.[index]
  180.         and set(key) (value) =
  181.             let index = positionDict.[key]
  182.             heapList.[index] <- new KeyValuePair<'TKey, 'TValue>(key, value)
  183.             heapifyUpDown index
  184.  
  185.     // Returns the count of the queue
  186.     member this.Count
  187.         with get() = heapList.Count
  188.  
  189.     // Resets the capacity of the Queue
  190.     member this.TrimExcess() =
  191.         heapList.TrimExcess()
  192.  
  193.     // Returns the capacity of the queue
  194.     member this.Capacity
  195.         with get() = heapList.Capacity
  196.  
  197.     // Clears the queue
  198.     member this.Clear() =
  199.         heapList.Clear()
  200.  
  201.  
  202.     // Standard IList members
  203.     interface ICollection<KeyValuePair<'TKey, 'TValue>> with
  204.  
  205.         member this.Add(item:KeyValuePair<'TKey, 'TValue>) =
  206.             this.Enqueue item.Key item.Value
  207.  
  208.         member this.Clear() =
  209.             heapList.Clear()
  210.  
  211.         member this.Contains(item:KeyValuePair<'TKey, 'TValue>) =
  212.             heapList.Contains(item)
  213.  
  214.         member this.Count
  215.             with get() = heapList.Count
  216.  
  217.         member this.CopyTo(toArray:KeyValuePair<'TKey, 'TValue>[], arrayIndex:int) =
  218.             heapList.CopyTo(toArray, arrayIndex)
  219.  
  220.         member this.IsReadOnly
  221.             with get() = false
  222.  
  223.         member this.Remove(item:KeyValuePair<'TKey, 'TValue>) =
  224.             let index = heapList.IndexOf(item)
  225.             if (inRange index).IsSome then
  226.                 deleteItem index
  227.                 true
  228.             else
  229.                 false
  230.  
  231.         member this.GetEnumerator() =
  232.             upcast heapList.GetEnumerator()
  233.  
  234.     // IEnumerable GetEnumerator implementation
  235.     interface IEnumerable with
  236.         member this.GetEnumerator() =  
  237.             upcast heapList.GetEnumerator()
      

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.

Written by Carl Nolan