Tukukkk

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();

    }

}