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

• t3chb0t: What is IMinHeap? Did you forget to include it? Your class also implements the IEnumerator<IMinHeap> GetEnumerator() API but the interface it implements is non-generic. Why this mismatch?
• WDUK: Oh sorry i thought i had added it at the bottom, my mistake. I have edited it in.

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?

• WDUK: Regarding the compare for popping, i always pop the left child since i sort them on insertion, the swaps makes sure the left is the correct priority over the right. I was not aware there was a standard implementation for this. I think i understand what you mean with the /2 to get parent index, i'm assuming the fix for that is to use indexes from 1 and up and leave 0 empty? Could you elaborate on This is exposing internal data to the whole world. Not sure what you mean by that since the interface implements the set priority - how else will an object have its priority set?e
• WDUK: Additionally you mention making it generic, not sure how that would work, i use an interface to set the priority on objects, how would i apply generics to it ?
• Peter Taylor: 1. "i always pop the left child since i sort them on insertion": but have you proved that cascading always maintains that invariant for the entire heap? I'm nervous about that. 2. Indexing from 1 is one way to solve the parent index problem. Alternatively, indexing from 0, the children of x are 2*x+1 and 2*x+2 and the parent is (x-1)/2. 3. Rather than take an IMinHeap as an argument, take the value and then wrap it in an IMinHeap inside the Insert method. That way the caller doesn't have access to it and can't change its priority.
• Peter Taylor: For a standard implementation, see Wikipedia or any algorithms textbook. For examples of generic heaps, see codereview.stackexchange.com/q/152998/1402 or codereview.stackexchange.com/q/84530/1402 . Given that you want to support updating priority, I would use a more general approach: BinaryHeap<TValue, TPriority> which has ctor BinaryHeap(IComparer<TPriority>) and methods Push(TValue, TPriority), Update(TValue, TPriority), TValue Pop().
• WDUK: Hm i'm not too familiar with the IComparer i'll have to research it.