PriorityQueue is a binary heap. Heap is commonly used algorithm. in some area such Graph shortest path and minimum spanning tree, it is very helpful.
both Java and C++ has PriorityQueue, but C# don’t have.
Here is a version of PriorityQueue
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | /// <summary> /// /// </summary> /// <typeparam name="T"></typeparam> public class PriorityQueue<T> where T : IComparable<T> { private List<T> data; private bool isMaxHeap = false; /// <summary> /// /// </summary> public PriorityQueue() { this.data = new List<T>(); } /// <summary> /// /// </summary> /// <param name="isMaxHeap"></param> public PriorityQueue(bool isMaxHeap) { this.data = new List<T>(); this.isMaxHeap = isMaxHeap; } /// <summary> /// /// </summary> /// <param name="item"></param> public void Enqueue(T item) { data.Add(item); int ci = data.Count - 1; // child index; start at end while (ci > 0) { int pi = (ci - 1) / 2; // parent index if(isMaxHeap) { if (data[ci].CompareTo(data[pi]) <= 0) break; } else if (data[ci].CompareTo(data[pi]) >= 0) break; // child item is larger than (or equal) parent so we're done T tmp = data[ci]; data[ci] = data[pi]; data[pi] = tmp; ci = pi; } } /// <summary> /// /// </summary> /// <returns></returns> public T Dequeue() { // assumes pq is not empty; up to calling code int li = data.Count - 1; // last index (before removal) T frontItem = data[0]; // fetch the front data[0] = data[li]; data.RemoveAt(li); --li; // last index (after removal) int pi = 0; // parent index. start at front of pq while (true) { int ci = pi * 2 + 1; // left child index of parent if (ci > li) break; // no children so done int rc = ci + 1; // right child if (isMaxHeap) { if (rc <= li && data[rc].CompareTo(data[ci]) >= 0) // if there is a rc (ci + 1), and it is smaller than left child, use the rc instead ci = rc; if (data[pi].CompareTo(data[ci]) >= 0) break; // parent is smaller than (or equal to) smallest child so done } else { if (rc <= li && data[rc].CompareTo(data[ci]) < 0) // if there is a rc (ci + 1), and it is smaller than left child, use the rc instead ci = rc; if (data[pi].CompareTo(data[ci]) <= 0) break; // parent is smaller than (or equal to) smallest child so done } T tmp = data[pi]; data[pi] = data[ci]; data[ci] = tmp; // swap parent and child pi = ci; } return frontItem; } /// <summary> /// /// </summary> /// <returns></returns> public T Peek() { T frontItem = data[0]; return frontItem; } /// <summary> /// /// </summary> /// <returns></returns> public int Count() { return data.Count; } public override string ToString() { string s = ""; for (int i = 0; i < data.Count; ++i) s += data[i].ToString() + " "; s += "count = " + data.Count; return s; } public bool IsConsistent() { // is the heap property true for all data? if (data.Count == 0) return true; int li = data.Count - 1; // last index for (int pi = 0; pi < data.Count; ++pi) // each parent index { int lci = 2 * pi + 1; // left child index int rci = 2 * pi + 2; // right child index if (lci <= li && data[pi].CompareTo(data[lci]) > 0) return false; // if lc exists and it's greater than parent then bad. if (rci <= li && data[pi].CompareTo(data[rci]) > 0) return false; // check the right child too. } return true; // passed all checks } // IsConsistent } |