14
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I have rewritten the class with suggestions from below, however being new here I'm unsure how to further share it. A new question would seem to not be called for but submitting it as an answer also seems to not be the right way. I'd like to get final feedback on the class just to see if my understanding of all that is here has been correct. How or where should I post the updated code for feedback? \$\endgroup\$ – BarelyTilted Jan 20 '17 at 23:38
12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I did not realise it would do that, wow that's a really great catch. I'll be sure to change it! \$\endgroup\$ – BarelyTilted Jan 19 '17 at 8:29
  • 5
    \$\begingroup\$ I think it's not only a performance bug, it's an API bug, since two elements could compare equal and you can't specify which to bubble! \$\endgroup\$ – user14393 Jan 19 '17 at 10:04
  • 1
    \$\begingroup\$ @Hurkyl But please note, that heaps are "unstable:" they maintain only a partial order, and, thus, cannot guarantee that two equal elements are popped in the same order as they were pushed. \$\endgroup\$ – coderodde Jan 19 '17 at 10:13
  • \$\begingroup\$ It took me awhile to get what you where getting at with Micro-Optimisation, it went over my head. I went through your provided code many times and I think I get the concept. The swap function became redundant once I started applying what you've suggested. I'll definitely try to remember that concept in the future! \$\endgroup\$ – BarelyTilted Jan 19 '17 at 12:55
  • 1
    \$\begingroup\$ Re: your "minor nitpick" -- your version is also better because of the rare corner case. CompareTo can return any number, including the smallest possible int. But the negative of the smallest possible int is still negative! Of course this doesn't happen in reality; you'd be perverse to return that value from a comparison. \$\endgroup\$ – Eric Lippert Jan 19 '17 at 15:46
8
\$\begingroup\$

You added , 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. :)

\$\endgroup\$
  • \$\begingroup\$ I'm sorta in the same boat I thought about making Clear() an expression function but I considered it as not returning anything so there wasn't a clear reason to use an expression over braces. Fair points on if statements I should be consistent, and less white space? Got it! Didn't notice the possibility of using an expression for ShouldSwap it makes sense too. Thanks for all your suggestions! :) \$\endgroup\$ – BarelyTilted Jan 19 '17 at 8:42
7
\$\begingroup\$
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.

\$\endgroup\$
  • 1
    \$\begingroup\$ @BarelyTilted are you sure you're a beginner? I wouldn't expect such stuff as sealed or readonly fields and/or properties or even expression body methods from someone who just started learning C# ;-] \$\endgroup\$ – t3chb0t Jan 19 '17 at 8:15
  • \$\begingroup\$ I like seeing positive feedback, that actually praises good code. Should do this more often myself. ^^ \$\endgroup\$ – Nikita B Jan 19 '17 at 8:22
  • \$\begingroup\$ @t3chb0t My only formal training was a 10 session course on c# basics. I'm doing a lot of extra research and experimentation hence why I'm here. :) I've never worked professionally, but I've been learning rapidly on the do and don'ts of programming. I consider myself a beginner still. Is that still considered a beginner? \$\endgroup\$ – BarelyTilted Jan 19 '17 at 8:24
  • \$\begingroup\$ @BarelyTilted as far as I'm concerned you're already at least intermediate. The code is too good for a beginner ;-) \$\endgroup\$ – t3chb0t Jan 19 '17 at 8:27
  • \$\begingroup\$ @t3chb0t thanks! I didn't expect so many people to reply and answer with such good suggestions, especially so quickly. It's been really great! \$\endgroup\$ – BarelyTilted Jan 19 '17 at 8:51
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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>();
}

\$\endgroup\$
  • \$\begingroup\$ That new in your answer will not compile. ;) \$\endgroup\$ – 410_Gone Jan 19 '17 at 7:39
  • \$\begingroup\$ I didn't consider using AsReadOnly() that is actually a good suggestion, would another answer suggests implementing IEnumerable and ICollection should that perhaps be done instead? \$\endgroup\$ – BarelyTilted Jan 19 '17 at 8:27
  • \$\begingroup\$ Yes, implementing IEnumerable is probably more intuitive than returning an read-only collection. \$\endgroup\$ – JanDotNet Jan 19 '17 at 9:30
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Fair points, I've modified my code to instead use IComparer<T> with the constructor instead of the Comparision<T>. I did not notice the NullReferenceException that could be thrown there. I am confused on the int.MinValue statement? What is MinValue? Also I've just learnt a new operator! Thank you for showing ?? \$\endgroup\$ – BarelyTilted Jan 19 '17 at 12:48
  • 1
    \$\begingroup\$ @BarelyTilted, int.MinValue is the smallest value which int can take: -2147483648. There's also int.MaxValue, which is the largest value which int can take: 2147483647. The fact that there's one more negative number than positive number is the reason that one of the negative numbers can't be negated. If you really want to get into details, to negate in twos complement you bit-invert and increment: -x == ~x + 1. The smallest representable value has bit representation 10000000000000000000000000000000, so inverting gives 01111111111111111111111111111111; then add with carry... \$\endgroup\$ – Peter Taylor Jan 19 '17 at 12:59
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Calling BinaryHeap.Elements.Add will not affect the collection in the heap, it only affects the version returned at that point in time. (Great thing about the List<T>(IEnumerable<T>) constructor, it copies the source to the new List<T>.) \$\endgroup\$ – 410_Gone Jan 19 '17 at 7:36
  • \$\begingroup\$ @EBrown, ah, you are right, of course, I have missed the new call. \$\endgroup\$ – Nikita B Jan 19 '17 at 7:38
  • \$\begingroup\$ I'm reinventing the wheel for educational purposes :), but I also didn't know of BinarySearch on Lists nor have I ever used a SortedList but from my understanding a SortedList must have unique keys how would I get around that if I did ever wish to use a sorted list to perform this function? \$\endgroup\$ – BarelyTilted Jan 19 '17 at 8:46
  • 1
    \$\begingroup\$ @BarelyTilted, this is tricky, but SortedList can be used for non-unioque items with some major limitations. However it looks like you have the case that actually fits those limitations. See: stackoverflow.com/a/21886340/1386995 . Personally, though, I would rather go the BinarySearch approach, if I were to pick one of the two. :) \$\endgroup\$ – Nikita B Jan 19 '17 at 9:52
  • \$\begingroup\$ Surely using BinarySearch or SortedList would give something other than a BinaryHeap (and would break the performance guarantees)? \$\endgroup\$ – Peter Taylor Jan 19 '17 at 11:30

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.