Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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;
    }
}
share|improve this question
    
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. – Snowbody Mar 20 '15 at 15:52
    
@Snowbody you are right. well this is my first post on codereview. I'm a noob lolz – KooKoo Mar 20 '15 at 15:57
up vote 7 down vote accepted
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.

share|improve this answer
    
Just about the HeapType, is just the name bad? Or is the idea of having a class that does two things wrong? – KooKoo Mar 20 '15 at 0:14
2  
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. – RubberDuck Mar 20 '15 at 0:17
    
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. – KooKoo Mar 20 '15 at 0:20
    
You're welcome! Welcome to CR btw. – RubberDuck Mar 20 '15 at 0:21

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

share|improve this answer

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.

share|improve this answer
    
What would you do in that case other than throwing another exception? – Snowbody Dec 1 '16 at 16:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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