Minimal generic min heap and priority queue implementation in C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// Minimal generic min heap and priority queue implementation in C#, in less than 100 lines of code | |
using System; | |
using System.Collections.Generic; | |
class MinHeap<T> where T : IComparable<T> | |
{ | |
private List<T> array = new List<T>(); | |
public void Add(T element) | |
{ | |
array.Add(element); | |
int c = array.Count - 1; | |
while (c > 0 && array[c].CompareTo(array[c / 2]) == -1) | |
{ | |
T tmp = array[c]; | |
array[c] = array[c / 2]; | |
array[c / 2] = tmp; | |
c = c / 2; | |
} | |
} | |
public T RemoveMin() | |
{ | |
T ret = array[0]; | |
array[0] = array[array.Count - 1]; | |
array.RemoveAt(array.Count - 1); | |
int c = 0; | |
while (c < array.Count) | |
{ | |
int min = c; | |
if (2 * c + 1 < array.Count && array[2 * c + 1].CompareTo(array[min]) == -1) | |
min = 2 * c + 1; | |
if (2 * c + 2 < array.Count && array[2 * c + 2].CompareTo(array[min]) == -1) | |
min = 2 * c + 2; | |
if (min == c) | |
break; | |
else | |
{ | |
T tmp = array[c]; | |
array[c] = array[min]; | |
array[min] = tmp; | |
c = min; | |
} | |
} | |
return ret; | |
} | |
public T Peek() | |
{ | |
return array[0]; | |
} | |
public int Count | |
{ | |
get | |
{ | |
return array.Count; | |
} | |
} | |
} | |
class PriorityQueue<T> | |
{ | |
internal class Node : IComparable<Node> | |
{ | |
public int Priority; | |
public T O; | |
public int CompareTo(Node other) | |
{ | |
return Priority.CompareTo(other.Priority); | |
} | |
} | |
private MinHeap<Node> minHeap = new MinHeap<Node>(); | |
public void Add(int priority, T element) | |
{ | |
minHeap.Add(new Node() { Priority = priority, O = element }); | |
} | |
public T RemoveMin() | |
{ | |
return minHeap.RemoveMin().O; | |
} | |
public T Peek() | |
{ | |
return minHeap.Peek().O; | |
} | |
public int Count | |
{ | |
get | |
{ | |
return minHeap.Count; | |
} | |
} | |
} |
The problem is an off-by-one in Add which throws off the heap order property, etc. To illustrate, given a tree structured like:
0
1---^---2
3-^-4 5-^-6
6 divided by 2 ends up misidentifying its parent as 3 instead of 2.
Tests should pass with:
public void Add(T element)
{
array.Add(element);
int c = array.Count - 1;
int parent = (c - 1) >> 1;
while (c > 0 && array[c].CompareTo(array[parent]) < 0)
{
T tmp = array[c];
array[c] = array[parent];
array[parent] = tmp;
c = parent;
parent = (c - 1) >> 1;
}
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hi, so I made a unit test for this and it's failing :( not sure what the fix is, but FYI.