You can learn about Priority Queue anywhere on the internet. Objective of this post is to give implementation of Priority Queue in C# as it is not available as standard library.
Implementation in C#:
public class PriorityQueue<T>
{
#region constructors
public PriorityQueue(int capacity, IComparer<T> comparer)
{
this.heap = new T[capacity > 0 ? capacity : DefaultCapacity];
this.count = 0;
this.comparer = comparer;
}
#endregion
#region public members
/// <summary>
/// Gets the number of items in the priority queue.
/// </summary>
public int Count
{
get { return count; }
}
/// <summary>
/// Gets the first or topmost object in the priority queue, which is the
/// object with the minimum value.
/// </summary>
public T Top
{
get
{
Debug.Assert(count > 0);
if (!isHeap)
{
Heapify();
}
return heap[0];
}
}
/// <summary>
/// Adds an object to the priority queue.
/// </summary>
public void Push(T value)
{
// Increase the size of the array if necessary.
if (count == heap.Length)
{
Array.Resize<T>(ref heap, count * 2);
}
// A common usage is to Push N items, then Pop them. Optimize for that
// case by treating Push as a simple append until the first Top or Pop,
// which establishes the heap property. After that, Push needs
// to maintain the heap property.
if (isHeap)
{
SiftUp(count, ref value, 0);
}
else
{
heap[count] = value;
}
count++;
}
/// <summary>
/// Removes the first node (i.e., the logical root) from the heap.
/// </summary>
public void Pop()
{
Debug.Assert(count != 0);
if (!isHeap)
{
Heapify();
}
if (count > 0)
{
--count;
// discarding the root creates a gap at position 0. We fill the
// gap with the item x from the last position, after first sifting
// the gap to a position where inserting x will maintain the
// heap property. This is done in two phases - SiftDown and SiftUp.
//
// The one-phase method found in many textbooks does 2 comparisons
// per level, while this method does only 1. The one-phase method
// examines fewer levels than the two-phase method, but it does
// more comparisons unless x ends up in the top 2/3 of the tree.
// That accounts for only n^(2/3) items, and x is even more likely
// to end up near the bottom since it came from the bottom in the
// first place. Overall, the two-phase method is noticeably better.
T x = heap[count]; // lift item x out from the last position
int index = SiftDown(0); // sift the gap at the root down to the bottom
SiftUp(index, ref x, 0); // sift the gap up, and insert x in its rightful position
heap[count] = default(T); // don't leak x
}
}
#endregion
#region private members
// sift a gap at the given index down to the bottom of the heap,
// return the resulting index
private int SiftDown(int index)
{
// Loop invariants:
//
// 1. parent is the index of a gap in the logical tree
// 2. leftChild is
// (a) the index of parent's left child if it has one, or
// (b) a value >= count if parent is a leaf node
//
int parent = index;
int leftChild = HeapLeftChild(parent);
while (leftChild < count)
{
int rightChild = HeapRightFromLeft(leftChild);
int bestChild =
(rightChild < count && comparer.Compare(heap[rightChild], heap[leftChild]) < 0) ?
rightChild : leftChild;
// Promote bestChild to fill the gap left by parent.
heap[parent] = heap[bestChild];
// Restore invariants, i.e., let parent point to the gap.
parent = bestChild;
leftChild = HeapLeftChild(parent);
}
return parent;
}
// sift a gap at index up until it reaches the correct position for x,
// or reaches the given boundary. Place x in the resulting position.
private void SiftUp(int index, ref T x, int boundary)
{
while (index > boundary)
{
int parent = HeapParent(index);
if (comparer.Compare(heap[parent], x) > 0)
{
heap[index] = heap[parent];
index = parent;
}
else
{
break;
}
}
heap[index] = x;
}
// Establish the heap property: heap[k] >= heap[HeapParent(k)], for 0<k<count
// Do this "bottom up", by iterating backwards. At each iteration, the
// property inductively holds for k >= HeapLeftChild(i)+2; the body of
// the loop extends the property to the children of position i (namely
// k=HLC(i) and k=HLC(i)+1) by lifting item x out from position i, sifting
// the resulting gap down to the bottom, then sifting it back up (within
// the subtree under i) until finding x's rightful position.
//
// Iteration i does work proportional to the height (distance to leaf)
// of the node at position i. Half the nodes are leaves with height 0;
// there's nothing to do for these nodes, so we skip them by initializing
// i to the last non-leaf position. A quarter of the nodes have height 1,
// an eigth have height 2, etc. so the total work is ~ 1*n/4 + 2*n/8 +
// 3*n/16 + ... = O(n). This is much cheaper than maintaining the
// heap incrementally during the "Push" phase, which would cost O(n*log n).
private void Heapify()
{
if (!isHeap)
{
for (int i = count / 2 - 1; i >= 0; --i)
{
// we use a two-phase method for the same reason Pop does
T x = heap[i];
int index = SiftDown(i);
SiftUp(index, ref x, i);
}
isHeap = true;
}
}
/// <summary>
/// Calculate the parent node index given a child node's index, taking advantage
/// of the "shape" property.
/// </summary>
private static int HeapParent(int i)
{
return (i - 1) / 2;
}
/// <summary>
/// Calculate the left child's index given the parent's index, taking advantage of
/// the "shape" property. If there is no left child, the return value is >= count.
/// </summary>
private static int HeapLeftChild(int i)
{
return (i * 2) + 1;
}
/// <summary>
/// Calculate the right child's index from the left child's index, taking advantage
/// of the "shape" property (i.e., sibling nodes are always adjacent). If there is
/// no right child, the return value >= count.
/// </summary>
private static int HeapRightFromLeft(int i)
{
return i + 1;
}
private T[] heap;
private int count;
private IComparer<T> comparer;
private bool isHeap;
private const int DefaultCapacity = 6;
#endregion
}
No comments:
Post a Comment