.Net Implementation of a Priority Queue (aka Heap)

Artigo
05/10/2012

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:

https://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:

namespace MSDN.FSharp
open System
open System.Collections
open System.Collections.Generic
type PriorityQueue<'TKey, 'TValue when 'TKey : comparison> private (data:IEnumerable<KeyValuePair<'TKey, 'TValue>> option, capacity:int, comparer:IComparer<'TKey>) =
let mutable heapList:List<KeyValuePair<'TKey, 'TValue>> = null
let mutable positionDict:Dictionary<'TKey, int> = null
// Determines if a value is in the heap
let inRange index =
if index >= 0 && index < heapList.Count then Some(index) else None
let checkIndex index =
if ((inRange index).IsNone) then raise (ArgumentException(sprintf "Index specified is not within range - %i" index))
// Gets the children of a node
let getChildren (index:int) =
// children left[2*pos] and right[2*pos + 1] where pos = index + 1
let left = (2 * index) + 1
let right = (2 * index) + 2
(inRange left, inRange right)
// Gets the parent of an index
let getParent (index:int) =
// parent index [pos/2] where index = pos - 1
if (index = 0) then None
else Some((index-1) / 2)
// Tests to see if the first value is greater than the first
let isGreater parent child =
if (comparer.Compare(heapList.[parent].Key, heapList.[child].Key) > 0) then true
else false
// Swaps two elements of the heap list
let swapElements idx1 idx2 =
let element1 = heapList.[idx1]
let element2 = heapList.[idx2]
heapList.[idx1] <- heapList.[idx2]
heapList.[idx2] <- element1
positionDict.[element1.Key] <- idx2
positionDict.[element2.Key] <- idx1
// Heapifys toward the parent
let rec heapifyUp (index:int) =
if (index > 0) then
let parent = getParent index
if (isGreater parent.Value index) then
swapElements parent.Value index
heapifyUp parent.Value
// Heapifys down to the children
let rec heapifyDown (index:int) =
let (left, right) = getChildren index
if (left.IsSome) then
let childindex =
if (right.IsSome && (isGreater left.Value right.Value)) then right.Value
else left.Value
if (isGreater index childindex) then
swapElements index childindex
heapifyDown childindex
// Heapifys down to the children
let heapifyUpDown (index:int) =
let parent = getParent index
if (parent.IsSome && (isGreater parent.Value index)) then
heapifyUp index
else
heapifyDown index
// Adds an items and heapifys
let insertItem (key:'TKey) (value:'TValue) =
let insertindex = heapList.Count
positionDict.Add(key, insertindex)
heapList.Add(new KeyValuePair<'TKey, 'TValue>(key, value))
heapifyUp(insertindex)
// Delete the root node and heapifys
let deleteItem index =
if (heapList.Count <= 1) then
heapList.Clear()
positionDict.Clear()
else
let lastindex = heapList.Count - 1
let indexKey = heapList.[index].Key
let lastKey = heapList.[lastindex].Key
heapList.[index] <- heapList.[lastindex]
positionDict.[lastKey] <- index
heapList.RemoveAt(lastindex)
positionDict.Remove(indexKey) |> ignore
heapifyDown index
// Default do bindings
do
if (comparer = null) then
raise (ArgumentException("Comparer cannot be null"))
let equalityComparer =
{ new IEqualityComparer<'TKey> with
override x.Equals(c1, c2) =
if ((comparer.Compare(c1, c2)) = 0) then true
else false
override x.GetHashCode(value) =
value.GetHashCode()
}
heapList <- new List<KeyValuePair<'TKey, 'TValue>>(capacity)
positionDict <- new Dictionary<'TKey, int>(capacity, equalityComparer)
if data.IsSome then
data.Value |> Seq.iter (fun item -> insertItem item.Key item.Value)
// Set of constructors
new() = PriorityQueue(None, 0, ComparisonIdentity.Structural<'TKey>)
new(capacity:int) = PriorityQueue(None, capacity, ComparisonIdentity.Structural<'TKey>)
new(data:IEnumerable<KeyValuePair<'TKey, 'TValue>>) = PriorityQueue(Some(data), 0, ComparisonIdentity.Structural<'TKey>)
new(comparer:IComparer<'TKey>) = PriorityQueue(None, 0, comparer)
new(capacity:int, comparer:IComparer<'TKey>) = PriorityQueue(None, capacity, comparer)
new(data:IEnumerable<KeyValuePair<'TKey, 'TValue>>, comparer:IComparer<'TKey>) = PriorityQueue(Some(data), 0, comparer)
// Checks to see if the heap is empty
member this.IsEmpty
with get() = (heapList.Count = 0)
// Enqueues a new entry into the heap
member this.Enqueue (key:'TKey) (value:'TValue) =
insertItem key value
()
// Peeks at the head of the heap
member this.Peek() =
if not(this.IsEmpty) then
heapList.[0]
else
raise (InvalidOperationException("Priority Queue is empty"))
// Dequeues the head entry into the heap
member this.Dequeue() =
let value = this.Peek()
deleteItem 0
value
// Determines whether an item is in the queue
member this.Contains (key:'TKey) (value:'TValue) =
heapList.Contains(new KeyValuePair<'TKey, 'TValue>(key, value))
// Returns the index of a specified item
member this.IndexOf (key:'TKey) (value:'TValue) =
heapList.IndexOf(new KeyValuePair<'TKey, 'TValue>(key, value))
// Removes an item from the queue at the specified index
member this.RemoveAt (index:int) =
checkIndex index
deleteItem index
// Determines whether an item is in the queue
member this.ContainsKey (key:'TKey) =
positionDict.ContainsKey key
// Determines whether an item is in the queue
member this.ChangeKey (key:'TKey) (value:'TKey)=
let index = positionDict.[key]
let item = heapList.[index]
heapList.[index] <- new KeyValuePair<'TKey, 'TValue>(value, item.Value)
positionDict.Remove(key) |> ignore
positionDict.Add(value, index)
heapifyUpDown index
// Removes an item from the queue for the specified key
member this.RemoveKey (key:'TKey) =
let index = positionDict.[key]
this.RemoveAt index
// Modifies elements based on index values
member this.Item
with get(key) =
let index = positionDict.[key]
heapList.[index]
and set(key) (value) =
let index = positionDict.[key]
heapList.[index] <- new KeyValuePair<'TKey, 'TValue>(key, value)
heapifyUpDown index
// Returns the count of the queue
member this.Count
with get() = heapList.Count
// Resets the capacity of the Queue
member this.TrimExcess() =
heapList.TrimExcess()
// Returns the capacity of the queue
member this.Capacity
with get() = heapList.Capacity
// Clears the queue
member this.Clear() =
heapList.Clear()
// Standard IList members
interface ICollection<KeyValuePair<'TKey, 'TValue>> with
member this.Add(item:KeyValuePair<'TKey, 'TValue>) =
this.Enqueue item.Key item.Value
member this.Clear() =
heapList.Clear()
member this.Contains(item:KeyValuePair<'TKey, 'TValue>) =
heapList.Contains(item)
member this.Count
with get() = heapList.Count
member this.CopyTo(toArray:KeyValuePair<'TKey, 'TValue>[], arrayIndex:int) =
heapList.CopyTo(toArray, arrayIndex)
member this.IsReadOnly
with get() = false
member this.Remove(item:KeyValuePair<'TKey, 'TValue>) =
let index = heapList.IndexOf(item)
if (inRange index).IsSome then
deleteItem index
true
else
false
member this.GetEnumerator() =
upcast heapList.GetEnumerator()
// IEnumerable GetEnumerator implementation
interface IEnumerable with
member this.GetEnumerator() =
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

Comments

Anonymous
May 12, 2012
This is great! Thanks. Btw wikipedia says: "It is a common misconception that a priority queue is a heap. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods."

Partilhar via

.Net Implementation of a Priority Queue (aka Heap)

Comments

Recursos adicionais