HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpModerate

Simple binary heap in C#

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
simplebinaryheap

Problem

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 where T : IComparable
{
    List items;

    public HeapType MinOrMax { get; private set; }

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

    public Heap(HeapType type)
    {
        items = new List();
        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  0) ^ flag)
                    largest = leftInd;
            }

            if (rightInd  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;
    }
}

Solution

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

Context

StackExchange Code Review Q#84530, answer score: 10

Revisions (0)

No revisions yet.