(Min)Heap implementation

Question

Being that I needed a min-heap implementation for a project, I implemented one. Now that it's finished I though about having a review for it. I'm interested in all aspects: readability, performance, naming, comments, everything.

I'm planning on extending it afterwards with other features like the possibility to choose between max and min heap, but for now it's just a min-heap and before extending it further I wanted a review of the current version.

public class Heap<TKey, TValue> : IQueue<KeyValuePair<TKey, TValue>>
{
    private readonly IList<KeyValuePair<TKey, TValue>> _heap 
        = new List<KeyValuePair<TKey, TValue>>();
    private Comparer<TKey> _keyComparer;

    /// <summary>
    /// Get the number of items in the Heap.
    /// </summary>
    public int Count => _heap.Count;

    /// <summary>
    /// The default constructor of a Heap.
    /// </summary>
    public Heap() 
        : this(Comparer<TKey>.Default, new Dictionary<TKey, TValue>())
    { }

    /// <summary>
    /// A constructor of a Heap.
    /// </summary>
    /// <param name="comparer">The comparer for TKey.</param>
    public Heap(Comparer<TKey> comparer)
        : this(comparer, new Dictionary<TKey, TValue>())
    { }

    /// <summary>
    /// A constructor of a Heap.
    /// </summary>
    /// <param name="comparer">The comparer for TKey.</param>
    /// <param name="elements">The initial elements of the Heap.</param>
    public Heap(Comparer<TKey> comparer, IEnumerable<KeyValuePair<TKey, TValue>> elements)
        : this(comparer, elements.ToDictionary(e => e.Key, e => e.Value))
    { }

    /// <summary>
    /// A constructor of a Heap.
    /// </summary>
    /// <param name="comparer">The comparer for TKey.</param>
    /// <param name="elements">The initial elements of the Heap.</param>
    public Heap(Comparer<TKey> comparer, IDictionary<TKey, TValue> elements)
    {
        _keyComparer = comparer;
        PushAll(elements);
    }

    /// <summary>
    /// Peek the next element in the Heap.
    /// </summary>
    public KeyValuePair<TKey, TValue> Peek()
    {
        return _heap.FirstOrDefault();
    }

    /// <summary>
    /// Pop the next element from the heap.
    /// </summary>
    /// <returns>The removed element.</returns>
    public KeyValuePair<TKey, TValue> Pop()
    {
        var element = Peek();

        if(!element.Equals(default(KeyValuePair<TKey, TValue>)))
        {
            RemoveFirst();
        }

        return element;
    }

    private void RemoveFirst()
    {
        int first = 0;
        int last = _heap.Count - 1;
        _heap.Swap(first, last);
        _heap.RemoveAt(last);
        SinkDown(first);
    }

    /// <summary>
    /// Push an element in the Heap.
    /// </summary>
    public void Push(KeyValuePair<TKey, TValue> element)
    {
        _heap.Add(element);
        BubbleUp(_heap.Count - 1);
    }

    private void BubbleUp(int index)
    {
        if (index == 0)
        {
            return;
        }

        int parentIndex = GetParentIndex(index);

        if (_keyComparer.Compare(_heap[index].Key, _heap[parentIndex].Key) < 0)
        {
            _heap.Swap(index, parentIndex);
            BubbleUp(parentIndex);
        }
    }

    private int GetParentIndex(int index)
    {
        return (index - 1) / 2;
    }

    /// <summary>
    /// Push the indicated elements in the Heap.
    /// </summary>
    public void PushAll(IEnumerable<KeyValuePair<TKey, TValue>> elements)
    {
        PushAll(elements.ToDictionary(e => e.Key, e => e.Value));
    }

    /// <summary>
    /// Push the indicated elements in the Heap.
    /// </summary>
    public void PushAll(IDictionary<TKey, TValue> elements)
    {
        elements.ForEach(e => Push(e));
    }

    /// <summary>
    /// Sink the element at the given index (0 based) if one of its children 
    /// is smaller than the element itself.
    /// </summary>
    /// <param name="index">The index of the element to sink down.</param>
    private void SinkDown(int index)
    {
        var element = _heap[index];
        Tuple<int, int> childrenIndices = GetChildrenIndices(index);
        int leftChildIndex = childrenIndices.Item1;
        int rightChildIndex = childrenIndices.Item2;

        if (leftChildIndex >= _heap.Count)
        {
            // This element has no children.
            return;
        }

        int indexOfElementToCompareWith = rightChildIndex < _heap.Count 
                                        ? GetPositionOfSmallestChild(leftChildIndex, rightChildIndex)
                                        : leftChildIndex;

        if (_keyComparer.Compare(element.Key, _heap[indexOfElementToCompareWith].Key) < 0)
        {
            _heap.Swap(index, indexOfElementToCompareWith);
            SinkDown(indexOfElementToCompareWith);
        }
    }

    private Tuple<int, int> GetChildrenIndices(int index)
    {
        int childrenBaseIndex = index * 2;
        return Tuple.Create(childrenBaseIndex + 1, childrenBaseIndex + 2);
    }

    private int GetPositionOfSmallestChild(int first, int second)
    {
        return _keyComparer.Compare(_heap[first].Key, _heap[second].Key) <= 0
            ? first
            : second;
    }
}

Answer 1

I didn't get your algorithm in detail, but I suppose you have a lot of unit tests to ensure that it works well ;).

My five cent:

• The instance variable _comparer can be read-only
• Instead of using the class Comparer<T>, you could use the more generic interface IComparer<T>.
• because you are using ToDictionary, the items can not have the same keys (would throw an DuplicatedKeyException). I am not sure if that is desired, but Wikipedia says:

In a min heap, the keys of parent nodes are less than or equal to those of the children

• Just a matter of taste: I would prefer out parameters or a custom type instead of a tuple because that is more readable.