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 functionalityA 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.
Binary Heap where a comparison delegate is used
c#;beginner;.net;generics;heap
Performance bugprivate 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: TrueMicro-optimization for bubbling methodsFor 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.