12
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ You accepted an answer after only an hour? That's your prerogative I guess, but usually on codereview.se people wait 24 hours to get a bunch of replies, then pick the most helpful or insightful one. Accepting an answer early might discourage other people from posting. \$\endgroup\$ – Snowbody Mar 20 '15 at 15:52
  • \$\begingroup\$ @Snowbody you are right. well this is my first post on codereview. I'm a noob lolz \$\endgroup\$ – KooKoo Mar 20 '15 at 15:57
  • \$\begingroup\$ A related post here implementing minHeap. \$\endgroup\$ – RBT Jan 6 '18 at 16:34
9
\$\begingroup\$
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.

\$\endgroup\$
  • \$\begingroup\$ Just about the HeapType, is just the name bad? Or is the idea of having a class that does two things wrong? \$\endgroup\$ – KooKoo Mar 20 '15 at 0:14
  • 2
    \$\begingroup\$ The idea of having a class that does two things is wrong. The name is just a signal that this is what's happening. (Of course, there are always exceptions to every rule.) Have you heard of the Single Responsibility Principle? It's often referenced when speaking of methods, but the idea applies to classes as well. Like I said, I'm not convinced inheritance is warranted here, but I think it's worth exploring. \$\endgroup\$ – RubberDuck Mar 20 '15 at 0:17
  • \$\begingroup\$ Yes you are right. I was just a bit lazy when I wrote this ;) so I thought a simple xor will do the job. thanks. \$\endgroup\$ – KooKoo Mar 20 '15 at 0:20
  • \$\begingroup\$ You're welcome! Welcome to CR btw. \$\endgroup\$ – RubberDuck Mar 20 '15 at 0:21
  • \$\begingroup\$ My 2 cents: There should be a Heap interface; then MinHeap and MaxHeap implementation classes. \$\endgroup\$ – code_dredd Oct 19 '18 at 23:18
10
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What would you do in that case other than throwing another exception? \$\endgroup\$ – Snowbody Dec 1 '16 at 16:47
3
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.