Binary Heap where a comparison delegate is used

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 so a Comparison 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((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 objects only.

• The heap must have Peek, Extract, Insert functionality

• A property on the inserted object must be used, using a KeyValuePair 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
{
private readonly List _elements;

private readonly Comparison _compare;

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

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

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

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

///
/// Initialises a new BinaryHeap with the specified compare function.
///
/// A method used to compare elements
public BinaryHeap(Comparison compare)
{
_compare = compare;
_elements = new List();
}

///
/// Initialises a new BinaryHeap as a copy of the passed in heap
///
/// The heap to copy
public BinaryHeap(BinaryHeap heap)
{
_elements = new List

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.

StackExchange Code Review Q#152998, answer score: 12