C# binary heap priority queue

Question

I made an A* pathfinder and it was too slow so i did some research into priority queues, i got it working but i am wondering if there is any improvements i can make for this class.

I opted to make a constructor that allows the option of min or max order, since it runs on the pathfinder the performance of this is quite crucial as well. So hopefully some one has some suggestions on ways to improve it.

Here is the class:

public class Heap : IEnumerable
{
    private readonly bool _isMinHeap;
    public readonly IMinHeap[] _items;
    private int _count;
    public int Size => _count;
    public Heap(int size, bool isMinHeap = true)
    {
        _items = new IMinHeap[size];
        _count = 0;
        _isMinHeap = isMinHeap;
    }

    public void Insert(IMinHeap item, int priority)
    {
        item.SetPriority(priority);
        if (Contains(item))
        {
            UpdateItem(item);
            return;
        }
        _items[_count] = item;
        item.HeapIndex = _count;
        _count++;
        CascadeUp(item);
    }

    private void UpdateItem(IMinHeap item)
    {
        int parentIndex = item.HeapIndex / 2;

        if (parentIndex > 0 && !HasCorrectParent(item.Value,_items[parentIndex].Value))
        {
            CascadeUp(item);
        }
        else
        {
            CascadeDown(item);
        }
    }
    public bool Contains(IMinHeap item)
    {
        if(item.HeapIndex < 0 || item.HeapIndex > _items.Length-1 || !Equals(_items[item.HeapIndex], item)) return false;
        return true;
    }
    /// <summary>
    /// Clear the priority queue and reset all nodes
    /// </summary>
    public void Wipe()
    {
        for (int i = 0; i < _items.Length; i++)
        {
            _items[i].HeapIndex = -1;
        }

        Array.Clear(_items,0,_items.Length);
        _count = 0;
    }
    /// <summary>
    /// Clear the priority but does not reset node indexes
    /// </summary>
    public void Clear()
    {
        Array.Clear(_items, 0, _items.Length);
        _count = 0;
    }

    public bool Pop(out IMinHeap item)
    {
        item = null;
        if (_count == 0)
            return false;

        item = _items[0];

        IMinHeap newRoot = _items[_count];
        _items[0] = newRoot;
        newRoot.HeapIndex = 0;

        _items[_count] = null;
        _count--;

        CascadeDown(newRoot);

        return true;

    }
    private void CascadeDown(IMinHeap item)
    {
        do
        {
            int childLeftIndex = item.HeapIndex * 2;
            int childRightIndex = childLeftIndex + 1;

            if (!HasCorrectChild(item.Value, _items[childLeftIndex]))
            {
                Swap(item.HeapIndex,childLeftIndex);
            }
            else if (!HasCorrectChild(item.Value, _items[childRightIndex]))
            {
                Swap(item.HeapIndex, childLeftIndex);
            }

            int parentIndex = item.HeapIndex / 2;
            SortChildren(parentIndex);

            if (!HasCorrectParent(item.Value, _items[parentIndex].Value))
            {
                Swap(item.HeapIndex, parentIndex);
            }
            else
            {
                return;
            }
        } while (true);
    }

    private bool HasCorrectChild(int itemValue, IMinHeap child)
    {
        return _isMinHeap && child.Value >= itemValue || !_isMinHeap && child.Value <= itemValue;
    }

    private void CascadeUp(IMinHeap item)
    {
        if (item.HeapIndex == 0) return; // there is no parents to look for
        do
        {
            int parentIndex = item.HeapIndex / 2;

            if (_items[parentIndex] == null) return;
            var parentValue = _items[parentIndex].Value;

            if (!HasCorrectParent(item.Value, parentValue))
            {
                Swap(item.HeapIndex, parentIndex);
                SortChildren(parentIndex);
            }
            else
            {
                return;
            }
        } while (true);
    }

    private void SortChildren(int parentIndex)
    {
        int leftChildIndex = 2 * parentIndex;
        int rightChildIndex = leftChildIndex + 1;

        var leftChild = _items[leftChildIndex];
        var rightChild = _items[rightChildIndex];

        if(leftChild == null || rightChild == null) //the parent has only one or no children - nothing to sort
            return; 
        else if(leftChild.Value > rightChild.Value && _isMinHeap || leftChild.Value < rightChild.Value && !_isMinHeap)
            Swap(leftChildIndex,rightChildIndex);
    }

    private void Swap(int itemIndexA, int itemIndexB)
    {
        var item = _items[itemIndexA];
        var parent = _items[itemIndexB];

        _items[itemIndexA] = parent;
        _items[itemIndexB] = item;

        parent.HeapIndex = itemIndexA;
        item.HeapIndex = itemIndexB;
    }

    private bool HasCorrectParent(int itemValue, int parentValue)
    {
        return _isMinHeap && parentValue <= itemValue || !_isMinHeap && parentValue >= itemValue;
    }

    public IEnumerator<IMinHeap> GetEnumerator()
    {
        for (int i = 0; i < _count; i++)
            yield return _items[i];
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Interface used for it:

public interface IMinHeap
{
    int HeapIndex { get; set; }
    int Value { get; }
    void SetPriority(int priority);
}

Answer 1

I opted to make a constructor that allows the option of min or max order, since it runs on the pathfinder the performance of this is quite crucial as well. So hopefully some one has some suggestions on ways to improve it.

Sure: take an IComparer (defaulting to Comparer<T>.Default if you have a simpler constructor which doesn't take one) and use that for all comparisons.

---

public class Heap : IEnumerable

Why is this not generic?

---

    private int _count;
    public int Size => _count;

Why not

    public int Size { get; private set; }

? And why Size rather than Count? It might even be worth implementing the full ICollection<T> interface.

---

    public void Insert(IMinHeap item, int priority)
    {
        item.SetPriority(priority);

Yikes! This is exposing internal data to the whole world. I could call Insert and then SetPriority and break your class.

---

    private void UpdateItem(IMinHeap item)
    {
        int parentIndex = item.HeapIndex / 2;

Are you sure? Bear in mind that C# arrays are indexed from 0, not 1.

---

    public bool Contains(IMinHeap item)
    {
        if(item.HeapIndex < 0 || item.HeapIndex > _items.Length-1 || !Equals(_items[item.HeapIndex], item)) return false;

Again, this is exposing internal data. If you want to implement Contains and UpdateItem without exposing internal data then the standard approach would be to wrap two data structures: an array for the heap itself and a Dictionary<T, int> for the heap index.

        return true;

But if you're going to do it this way, why not invert the test and just have

    public bool Contains(IMinHeap item) => item.HeapIndex >= 0 && item.HeapIndex < _items.Length && Equals(_items[item.HeapIndex], item);

? That seems clearer to me.

---

    /// <summary>
    /// Clear the priority queue and reset all nodes
    /// </summary>
    public void Wipe()

    /// <summary>
    /// Clear the priority but does not reset node indexes
    /// </summary>
    public void Clear()

I'm puzzled as to why both are needed.

---

    public bool Pop(out IMinHeap item)

I would prefer public T Pop() and throw an exception if it's empty. If I implemented this method I'd call it TryPop. IMO that's more consistent with the standard library.

---

    private void CascadeDown(IMinHeap item)
    {
        do
        {
            int childLeftIndex = item.HeapIndex * 2;
            int childRightIndex = childLeftIndex + 1;

Again, are you sure?

            if (!HasCorrectChild(item.Value, _items[childLeftIndex]))
            {
                Swap(item.HeapIndex,childLeftIndex);
            }
            else if (!HasCorrectChild(item.Value, _items[childRightIndex]))
            {
                Swap(item.HeapIndex, childLeftIndex);
            }

            int parentIndex = item.HeapIndex / 2;
            SortChildren(parentIndex);

I'm really not convinced that this is correct. The standard implementation is to first compare the left and right children to work out which should be popped first, and then compare just that one with the parent.

Incidentally, what tests do you have for the queue?

---

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

You used => notation earlier: why not use it here?