Skip to content

Instantly share code, notes, and snippets.

@ashish01
Last active March 29, 2022 06:11
  • Star 5 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save ashish01/8593936 to your computer and use it in GitHub Desktop.
Minimal generic min heap and priority queue implementation in C#
/// 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;
}
}
}
@swax
Copy link

swax commented Dec 19, 2015

Hi, so I made a unit test for this and it's failing :( not sure what the fix is, but FYI.

        // add 1000 random numbers
        var list = new List<int>();
        var heap = new PriorityQueue<int>();
        var rnd = new Random();

        while (list.Count < 1000)
        {
            var priority = rnd.Next(1, 1000000);

            list.Add(priority);
            heap.Add(priority, priority);
        }

        // sort 10 k numbers
        list = list.OrderBy(p => p).ToList();

        // pull numbers from heap
        var currentIndex = 0;
        var mismatch = 0;
        var heapList = new List<string>();

        while (heap.Count > 0)
        {
            var priority = heap.RemoveMin();

            var expected = list[currentIndex];


            heapList.Add(priority + " / " + expected);

            // verify they match the sequence
            //Debug.Assert(priority == expected);
            if (priority != expected)
                mismatch++;

            currentIndex++;
        }

        Debug.Assert(mismatch == 0);

@jcheatham
Copy link

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