# .Net Implementation of a Priority Queue (aka Heap)

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

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