Simple binary heap in C#

Question

I've written a simple binary heap in C# and I want to know if it has any problems or if I can make it better.

public enum HeapType
{
    MinHeap,
    MaxHeap
}

public class Heap<T> where T : IComparable<T>
{
    List<T> items;

    public HeapType MinOrMax { get; private set; }

    public T Root
    {
        get { return items[0]; }
    }

    public Heap(HeapType type)
    {
        items = new List<T>();
        this.MinOrMax = type;
    }

    public void Insert(T item)
    {
        items.Add(item);

        int i = items.Count - 1;

        bool flag = true;
        if (MinOrMax == HeapType.MaxHeap)
            flag = false;

        while(i > 0)
        {
            if ((items[i].CompareTo(items[(i - 1) / 2]) > 0) ^ flag)
            {
                T temp = items[i];
                items[i] = items[(i - 1) / 2];
                items[(i - 1) / 2] = temp;
                i = (i - 1) / 2;
            }
            else
                break;
        }
    }

    public void DeleteRoot()
    {
        int i = items.Count - 1;

        items[0] = items[i];
        items.RemoveAt(i);

        i = 0;

        bool flag = true;
        if (MinOrMax == HeapType.MaxHeap)
            flag = false;

        while(true)
        {
            int leftInd = 2 * i + 1;
            int rightInd = 2 * i + 2;
            int largest = i;

            if (leftInd < items.Count)
            {
                if ((items[leftInd].CompareTo(items[largest]) > 0) ^ flag)
                    largest = leftInd;
            }

            if (rightInd < items.Count)
            {
                if ((items[rightInd].CompareTo(items[largest]) > 0) ^ flag)
                    largest = rightInd;
            }

            if (largest != i)
            {
                T temp = items[largest];
                items[largest] = items[i];
                items[i] = temp;
                i = largest;
            }
            else
                break;
        }
    }

    public T PopRoot()
    {
        T result = items[0];

        DeleteRoot();

        return result;
    }
}

Answer 1

public HeapType MinOrMax { get; private set; }

I'm wary of any name that has the words And or Or in it. It often indicates that something has too many responsibilities. Names like HeapType inside of a Heap class are also indicative that you should be considering some inheritance and an OOP approach.

I'm not saying for sure that it's better, but you may want to consider using an abstract base class that both MinHeap and MaxHeap derive their common functionality from.

if (MinOrMax == HeapType.MaxHeap)
    flag = false;

Use brackets friend. Always use brackets. Better yet, do away with the if entirely and assign the result of an expression to your flag.

flag = !(MinOrMax == HeapType.MaxHeap);

You calculate this value several times within several lines of code.

(i - 1) / 2

It would be better to calculate it once and assign the result to a well named variable.

Answer 2

I note that you're restricting your types T to those that are IComparable, that is, those that implement CompareTo. A more general solution would allow the caller to specify their own IComparer which may be that type's CompareTo or may be something else entirely.

Also see https://stackoverflow.com/questions/14336416/using-icomparer-for-sorting

Answer 3

DeleteRoot() method should be marked with private access as shown below:

private void DeleteRoot()

DeleteRoot() method is an internal implementation detail of the class which is used by PopRoot() method. Outside world consuming the Heap<T> class should see only PopRoot() method to remove the minimum or maximum element in the heap. It is very confusing that currently there are two ways to delete the root node in your heap binary tree implementation.

Answer 4

Maybe also add a check in PopRoot() to see if there are still items left in the List. Otherwise, popping until the list is empty is not possible without an exception being thrown.

Answer 5

You could use delegates here where you have

public delegate bool Comparator(T a,T b);

This would replace

public HeapType MinOrMax { get; private set; }

The user would pass in a function that compares the 2 objects and returns a true or false

 if (comparator.Invoke(items[i],items[(i - 1) / 2]))

this would allow anything about these 2 objects to be tested and then a result to be returned based on this decision. This would make it more fluid, but of course this may be more complicated than needed for some uses.