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.<\/p>\n
both Java and C++ has PriorityQueue, but C# don’t have. <\/p>\n
Here is a version of PriorityQueue<\/p>\n
\r\n\/\/\/ \r\n \/\/\/ \r\n \/\/\/ <\/summary>\r\n \/\/\/ <\/typeparam>\r\n public class PriorityQueue where T : IComparable\r\n {\r\n private List data;\r\n private bool isMaxHeap = false; \r\n \/\/\/ \r\n \/\/\/ \r\n \/\/\/ <\/summary>\r\n public PriorityQueue()\r\n {\r\n this.data = new List();\r\n }\r\n\r\n \/\/\/ \r\n \/\/\/ \r\n \/\/\/ <\/summary>\r\n \/\/\/ <\/param>\r\n public PriorityQueue(bool isMaxHeap)\r\n {\r\n this.data = new List();\r\n this.isMaxHeap = isMaxHeap;\r\n }\r\n\r\n \/\/\/ \r\n \/\/\/ \r\n \/\/\/ <\/summary>\r\n \/\/\/ <\/param>\r\n public void Enqueue(T item)\r\n {\r\n data.Add(item);\r\n int ci = data.Count - 1; \/\/ child index; start at end\r\n while (ci > 0)\r\n {\r\n int pi = (ci - 1) \/ 2; \/\/ parent index\r\n if(isMaxHeap)\r\n {\r\n if (data[ci].CompareTo(data[pi]) <= 0) break;\r\n } else if (data[ci].CompareTo(data[pi]) >= 0)\r\n break; \/\/ child item is larger than (or equal) parent so we're done\r\n T tmp = data[ci]; data[ci] = data[pi]; data[pi] = tmp;\r\n ci = pi;\r\n }\r\n }\r\n \/\/\/ \r\n \/\/\/ \r\n \/\/\/ <\/summary>\r\n \/\/\/ <\/returns>\r\n public T Dequeue()\r\n {\r\n \/\/ assumes pq is not empty; up to calling code\r\n int li = data.Count - 1; \/\/ last index (before removal)\r\n T frontItem = data[0]; \/\/ fetch the front\r\n data[0] = data[li];\r\n data.RemoveAt(li);\r\n\r\n --li; \/\/ last index (after removal)\r\n int pi = 0; \/\/ parent index. start at front of pq\r\n while (true)\r\n {\r\n int ci = pi * 2 + 1; \/\/ left child index of parent\r\n if (ci > li) break; \/\/ no children so done\r\n int rc = ci + 1; \/\/ right child\r\n if (isMaxHeap)\r\n {\r\n 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\r\n ci = rc;\r\n if (data[pi].CompareTo(data[ci]) >= 0) break; \/\/ parent is smaller than (or equal to) smallest child so done\r\n }\r\n else\r\n {\r\n\r\n 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\r\n ci = rc;\r\n if (data[pi].CompareTo(data[ci]) <= 0) break; \/\/ parent is smaller than (or equal to) smallest child so done\r\n }\r\n\r\n T tmp = data[pi]; data[pi] = data[ci]; data[ci] = tmp; \/\/ swap parent and child\r\n pi = ci;\r\n }\r\n return frontItem;\r\n }\r\n\r\n \/\/\/ \r\n \/\/\/ \r\n \/\/\/ <\/summary>\r\n \/\/\/ <\/returns>\r\n public T Peek()\r\n {\r\n T frontItem = data[0];\r\n return frontItem;\r\n }\r\n\r\n \/\/\/ \r\n \/\/\/ \r\n \/\/\/ <\/summary>\r\n \/\/\/ <\/returns>\r\n public int Count()\r\n {\r\n return data.Count;\r\n }\r\n\r\n public override string ToString()\r\n {\r\n string s = \"\";\r\n for (int i = 0; i < data.Count; ++i)\r\n s += data[i].ToString() + \" \";\r\n s += \"count = \" + data.Count;\r\n return s;\r\n }\r\n\r\n public bool IsConsistent()\r\n {\r\n \/\/ is the heap property true for all data?\r\n if (data.Count == 0) return true;\r\n int li = data.Count - 1; \/\/ last index\r\n for (int pi = 0; pi < data.Count; ++pi) \/\/ each parent index\r\n {\r\n int lci = 2 * pi + 1; \/\/ left child index\r\n int rci = 2 * pi + 2; \/\/ right child index\r\n\r\n if (lci <= li && data[pi].CompareTo(data[lci]) > 0) return false; \/\/ if lc exists and it's greater than parent then bad.\r\n if (rci <= li && data[pi].CompareTo(data[rci]) > 0) return false; \/\/ check the right child too.\r\n }\r\n return true; \/\/ passed all checks\r\n } \/\/ IsConsistent\r\n }\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"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 … Continue reading