2
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Is a min-heap equivalent to a priority queue? If not could you please explain (or provide a link) how exactly a min-heap behaves? \$\endgroup\$ – JanDotNet May 13 '16 at 14:48
  • 1
    \$\begingroup\$ @JNS a heap is a data structure you could use to implement a priority queue. Depending on the relation between parent and child nodes (greater than or equal to, or the opposite) you have max heaps or min heaps. Here you can find a description of a min heap or max heap. \$\endgroup\$ – Gentian Kasa May 13 '16 at 14:55
  • \$\begingroup\$ @JNS a heap is a binary tree (you can see it as a special type of graph though) with a certain relation (see previous comment) among parent and child nodes. By managing it through a linear structure (the List in this case) you just have to arrange the indices of the nodes. See GetChildrenIndices and GetParentIndex for the rule on how the indices are arranged. This page may be more helpful than the previous. \$\endgroup\$ – Gentian Kasa May 13 '16 at 15:35
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Nice catch on the bug. I hadn't built any test for that specific case. Thanks. \$\endgroup\$ – Gentian Kasa May 13 '16 at 16:13

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.