Binary Heap where a comparison delegate is used

Question

I currently have a Generic Implementation of a BinaryHeap. It must be able to maintain it's integrity with elements that may or may not implement IComparable<T> so a Comparison<T> delegate is used allowing the specification of a compare function at creation for the contained elements. So an example call would be:

var heap = new BinaryHeap<Message>((m1, m2) => -(m1.Priority.CompareTo(m2.Priority)))

Where the Priority property of messages is compared by default the heap works in a min fashion but by inverting the result of the comparison here it is working as a max heap instead.

There are a few requirements for the class to follow:

• It must be able to work with any type, and not be constricted to using IComparable<T> objects only.
• The heap must have Peek, Extract, Insert functionality
• A property on the inserted object must be used, using a KeyValuePair<TKey,TValue> is not an option (However, this is only required by the public interface, would extracting properties into keys be more efficient?)

---

public sealed class BinaryHeap<T>
{
    private readonly List<T> _elements;

    private readonly Comparison<T> _compare;

    /// <summary>
    /// The amount of elements in the heap
    /// </summary>
    public int Count => _elements.Count;

    /// <summary>
    /// A read only list of elements
    /// </summary>
    public List<T> Elements => new List<T>(_elements);

    /// <summary>
    /// Returns the method that dictates how elements are compared
    /// </summary>
    public Comparison<T> Compare => _compare;

    /// <summary>
    /// Clears the heap of all elements
    /// </summary>
    public void Clear() { _elements.Clear(); }

    /// <summary>
    /// Initialises a new BinaryHeap with the specified compare function.
    /// </summary>
    /// <param name="compare">A method used to compare elements</param>
    public BinaryHeap(Comparison<T> compare)
    {
        _compare = compare;
        _elements = new List<T>();
    }

    /// <summary>
    /// Initialises a new BinaryHeap as a copy of the passed in heap
    /// </summary>
    /// <param name="heap">The heap to copy</param>
    public BinaryHeap(BinaryHeap<T> heap)
    {
        _elements = new List<T>(heap.Elements);
        _compare = heap.Compare;
    }

    /// <summary>
    /// Extracts the root
    /// </summary>
    /// <returns>The topmost object of the heap</returns>
    public T Extract()
    {
        if (_elements.Count == 0) throw new InvalidOperationException("The heap contains no elements");
        T node = _elements[0];

        if (_elements.Count <= 2)
            _elements.RemoveAt(0);
        else
        {
            _elements[0] = _elements[_elements.Count - 1];
            _elements.RemoveAt(_elements.Count - 1);
            BubbleDown(_elements[0]);
        }

        return node;
    }
    /// <summary>
    /// Inserts an element onto the heap
    /// </summary>
    /// <param name="entry">The object to add</param>
    public void Insert(T entry)
    {
        _elements.Add(entry);
        if ((_elements.Count - 1) == 0)
            return;

        BubbleUp(entry);

    }
    /// <summary>
    /// Peeks at the topmost object of the heap
    /// </summary>
    /// <returns>The top most object of the heap</returns>
    public T Peek()
    {
        //If a heap doesn't have any elements throw an exception
        if (_elements.Count == 0)
            throw new InvalidOperationException("The heap contains no elements");
        return _elements[0];
    }

    /// <summary>
    /// Should Element1 be swapped with Element2 based on our Compare Delegate
    /// </summary>
    /// <returns>true if it should, false if it should not</returns>
    private bool ShouldSwap(T element1, T element2)
    {
        var comparision = Compare(element1, element2);
        return comparision <= 0;
    }

    /// <summary>
    /// Swaps Element1 with Element2
    /// </summary>
    private void Swap(T element1, T element2)
    {
        //Swap the first element with the second
        int indexOfSecond = _elements.IndexOf(element2);
        _elements[_elements.IndexOf(element1)] = element2;
        _elements[indexOfSecond] = element1;


    }

    /// <summary>
    /// Bubbles the specified element down the heap until the heaps properties are restored
    /// </summary>
    /// <param name="element">The Element to bubble down</param>
    private void BubbleDown(T element)
    {
        int elementIndex = _elements.IndexOf(element), minElementIndex = 0;

        while (true)
        {
            int childLeftIndex = 2 * elementIndex + 1;

            //If the Child index exists outside the amount of elements in the heap then
            //the element is already at the bottom of the heap so we should break.
            if (childLeftIndex >= _elements.Count)
                break;

            element = _elements[elementIndex];
            var childElement = _elements[childLeftIndex];

            if (ShouldSwap(childElement, element))
                minElementIndex = childLeftIndex;

            int childRightIndex = childLeftIndex + 1;

            //If the right child exists it must be checked as well
            if (childRightIndex < _elements.Count)
            {

                element = _elements[minElementIndex];
                childElement = _elements[childRightIndex];

                if (ShouldSwap(childElement, element))
                    minElementIndex = childRightIndex;
            }


            //If the minimum Element is still the original element of the loop
            //then the heap properties has been restored and we should break
            if (elementIndex == minElementIndex)
                break;

            //Since our element is out of order and violating the heaps properties it should be swapped
            Swap(_elements[elementIndex], _elements[minElementIndex]);


            elementIndex = minElementIndex;
        }

    }
    /// <summary>
    /// Bubbles an Element up the heap until the heaps properties are restored
    /// </summary>
    /// <param name="element">The element to bubble up</param>
    private void BubbleUp(T element)
    {
        int elementIndex = _elements.IndexOf(element);

        while (elementIndex > 0)
        {
            int parentIndex = (elementIndex - 1) / 2;

            T elementParent = _elements[parentIndex];
            if (ShouldSwap(element, elementParent))
            {
                Swap(element, elementParent);
                elementIndex = parentIndex;
            }
            else break;
        }

        _elements[elementIndex] = element;
    }


}

What I am most concerned about is the readability of the BubbleDown function, it looks 'ugly' to me but I'm unsure how to refactor it, would recursion be applicable here? If so would it reduce the performance of the class? What would be some possible optimisations that could be performed? This isn't a speed critical class but should still try to perform well.

Answer 1

Performance bug

private void BubbleUp(T element)
{
    int elementIndex = _elements.IndexOf(element);
    ...

This is \$O(n)\$, which completely oblitirates \$O(\log n)\$. (It takes over a second on 2,5 GHz CPU to insert 10 000 elements using your version.) Same applies to BubbleDown.

Instead of passing the element to BubbleUp and BuggleDown, pass the index of the element and start bubbling up or down from the position described by the index.

Next, the swapping routine:

private void Swap(T element1, T element2)
{
    //Swap the first element with the second
    int indexOfSecond = _elements.IndexOf(element2);
    _elements[_elements.IndexOf(element1)] = element2;
    _elements[indexOfSecond] = element1;
}

Same issue here as well. Just rewrite to

private void Swap(int index1, int index2)
{
    T tmp = _elements[index1];
    _elements[index1] = _elements[index2];
    _elements[index2] = tmp;
}

For the sake of education, I have prepared a C# program: https://gist.github.com/coderodde/1b601ecc9ca4cf66692392912a17f39f (updated)

The output is something like:

Inserting into OP heap: 12373 milliseconds.
Inserting into slower coderodde heap: 9 milliseconds.
Inserting into coderodde heap: 10 milliseconds.
Popped OP heap in 10054 milliseconds.
Popped slow coderodde heap in 80 milliseconds.
Popped coderodde heap in 55 milliseconds.
Heaps agree: True

Micro-optimization for bubbling methods

For example, consider the bubble up method: you compare the current element with its parent, and swap them if needed. Swapping takes 3 assignments. Instead you could cache the element to bubble up, and if its parent has lower priority, you just move the parent to the place of the element. Next you compare the element to the parent of parent; if invariant is still wrong, push parent of parent to parent, and so on. The idea here is that instead of \$n\$ swaps (each taking 3 assignments; total of \$3n\$ assignments) you do only \$n\$. (You can think of it like rotating a path from new location to the correct location in the heap.)

In the above sample output SlowerCoderoddeBinaryHeap does the swaps, and CoderoddeBinaryHeap do the rotation trick.

Minor neatpick

(m1, m2) => -(m1.Priority.CompareTo(m2.Priority))

I believe you can write instead:

(m1, m2) => (m2.Priority.CompareTo(m1.Priority))

Hope that helps.

Answer 2

You added beginner, so I'm going to give you a few pointers to start with, to help you work from.

---

First: C#6.0 (which I see you are using) allows void methods to be expressions as well as ones with a return type.

public void Clear() { _elements.Clear(); }

To:

public void Clear() => _elements.Clear();

You may or may not want to do this, I don't like it because => to me means 'returns' but you might like it, and it's my job to educate you if I can. :)

---

public T Extract()
{
    if (_elements.Count == 0) throw new InvalidOperationException("The heap contains no elements");
    T node = _elements[0];

    if (_elements.Count <= 2)
        _elements.RemoveAt(0);
    else
    {
        _elements[0] = _elements[_elements.Count - 1];
        _elements.RemoveAt(_elements.Count - 1);
        BubbleDown(_elements[0]);
    }

    return node;
}

I don't mind omitting braces on if statements, but do not do either of the following:

1. Inline the condition and the action;
2. Omit braces if there is an else or else if;

So, let's take that first if and make it:

if (_elements.Count == 0)
    throw new InvalidOperationException("The heap contains no elements");

That's fine, I like that for input guards.

The second:

if (_elements.Count <= 2)
{
    _elements.RemoveAt(0);
}
else
{

That's fine as well.

---

public void Insert(T entry)
{
    _elements.Add(entry);
    if ((_elements.Count - 1) == 0)
        return;

    BubbleUp(entry);

}

Two issues:

1. The parenthesis around _elements.Count - 1 are unnecessary;
2. The extra space after BubbleUp(entry); should be removed;

Generally, we want as little whitespace as necessary. I don't ever put whitespace after a { or before a } unless that body is blank, and I don't ever use more than one line.

---

private bool ShouldSwap(T element1, T element2)
{
    var comparision = Compare(element1, element2);
    return comparision <= 0;
}

That intermediary variable is unnecessary:

private bool ShouldSwap(T element1, T element2) =>
    Compare(element1, element2) <= 0;

---

if (ShouldSwap(element, elementParent))
{
    Swap(element, elementParent);
    elementIndex = parentIndex;
}
else break;

I kind of talked about this. Let's make that else block in a brace set:

if (ShouldSwap(element, elementParent))
{
    Swap(element, elementParent);
    elementIndex = parentIndex;
}
else
{
    break;
}

Only because it's easy to miss without braces here.

---

Overall, great start! I really do hope you explore C# more and learn more of the language. :)

Answer 3

public sealed class BinaryHeap<T>  

Well done. Using sealed if you don't intend to inherit from this class thats the way to go.

private readonly List<T> _elements;

private readonly Comparison<T> _compare;  

Marking fields which should not change with readonly is good.

int elementIndex = _elements.IndexOf(element), minElementIndex = 0;  

Don't declare multiple variables on the same line. It makes the code harder to read.

---

In the BubbleDown() method you have

           childElement = _elements[childRightIndex];  

whereas in the BubbleUp() method you have

           T elementParent = _elements[parentIndex];  

I would suggest renaming elementParent to parentElement to be consistent in the naming.

---

public void Insert(T entry)
{
    _elements.Add(entry);
    if ((_elements.Count - 1) == 0)
        return;

    BubbleUp(entry);

}  

The if condition could be simplified to

if (_elements.Count == 1)  

---

Using braces {} had already been mentioned by @EBrown but I would like to take it further. I would like to encourage you to always use them. This makes your code less error prone because omiting braces can lead to hidden bugs which are hard to track.

Answer 4

Bug

As a corollary to the performance bug that coderodde found, there is also an actual bug in the same place:

private void BubbleUp(T element)
{
    int elementIndex = _elements.IndexOf(element);
    ...

Not only is it slow to search for the element, it is wrong to do so as well. If you add a duplicate element, the search will find the element that already exists instead of the one you just added to the end. This will result in the newly added element not getting bubbled up. Instead of this function taking a T element, it should take an int elementIndex instead.

Almost a bug

This code is also somewhat wrong for a different reason:

private void BubbleDown(T element)
{
    int elementIndex = _elements.IndexOf(element), minElementIndex = 0;
    ...

Here, you should have initialized minElementIndex to elementIndex instead of to 0. If the element is less than both of its children, then this later check:

        if (elementIndex == minElementIndex)
            break;

might have failed spuriously because it was comparing versus index 0, and then you would have ended up swapping the given element with slot [0]. The only reason this isn't a bug is because you only ever call BubbleDown on the first element.

Also, as with the other function, this one should take an index as its argument.

Answer 5

public List<T> Elements => new List<T>(_elements);

You can just call AsReadOnly() to get a read-only instance of the list:

public ReadOnlyCollection<T> Elements => _elements.AsReadOnly();

---

Even if it is possible to specify a Comparison<T>, it would be nice to have a parameter less constructor that uses the default comparer of T

public BinaryHeap()
{
    compare = (x, y) => Comparer<T>.Default.Compare(x, y);
    _elements = new List<T>();
}

---

Answer 6

I'm going to try to only pick up points which no-one has mentioned yet.

• It must be able to work with any type, and not be constricted to using IComparable<T> objects only.

That's a reasonable requirement, but the code goes further:

public BinaryHeap(Comparison<T> compare)
{
    _compare = compare;

One possible improvement would be to observe that you require _compare to be non-null (otherwise ShouldSwap throws a NullReferenceException) and so the constructor should enforce that:

public BinaryHeap(Comparison<T> compare)
{
    if (compare == null) throw new ArgumentNullException(nameof(compare));
    _compare = compare;

IMO a better improvement is to say that where the type does implement IComparable<T> you shouldn't require the caller to implement a comparer. There's a useful item in the standard API for this: Comparer<T>.Default. There's a slight impedance mismatch, but it's possible to convert Comparison<T> to Comparer<T> or vice versa. For consistency with System.Collections.Generic I would favour

public BinaryHeap(IComparer<T> comparer)
{
    _Comparer = comparer ?? Comparer<T>.Default;

---

On the subject of comparers, there may be a subtle bug in the example

var heap = new BinaryHeap<Message>((m1, m2) => -(m1.Priority.CompareTo(m2.Priority)))

Although may implementations of CompareTo return one of -1, 0, 1, they can legally return any integer, including MinValue. One thing which catches many people out is that -int.MinValue == int.MinValue. If you know the type of Priority and the implementation of its CompareTo then it may be safe.

---

ShouldSwap is not a useful name. Whether or not you should swap the elements depends on factors which are outside the scope of that method. But abstracting it does serve one purpose: it makes it clear that there's a micro-optimisation. If two elements compare equal (0) then there's nothing gained by swapping them, so I would favour < over <= and a rename to IsLessThan.

Answer 7

Instead of exposing your collection via Elements property, you should implement appropriate interfaces on BinaryHeap itself, such as IEnumerable<T> (or ICollection<T>, or w/e depending on what you want to expose) and make the underlying collection private. This:

    var heap = new BinaryHeap(...);
    foreach (var element in heap)

should be a valid code.