I was trying to implement a generic PriorityQueue in C#. Below is my implementation which works fine as per few test cases. Operations supported-
- Add: Adds an element
- Poll: Removes the smallest element and returns it
- Remove: Removes a specific element (only first occurence) and returns it
- Clear: Clears all elements
- Contains: Return true if the element is found else false
Code:
// Complete binary tree, smallest/largest at the top
// Canonical representation using array
// LeftIndex = 2 * ParentIndex + 1
// RightIndex = 2 * ParentIndex + 2
// Insert always in bottom-left order, filling up the level (row). Last position in array/linked list
// After insert at root (end) sift-up/swim to maintain heap-invariant by sawapping
// Poll happens at root (first) position by swapping with the last element
// SiftDown after removing element: Swap parent and smaller child. If same, choose left. SiftDown till lastIndex or heap variant stisfied
// Remove(element): Linear search the element. Swap the node with the last node then remove last node. SiftUp (if bubble up) or SiftDown (bubble down)
public class PriorityQueue<T> where T : IComparable<T>
{
public int Length { get; private set; }
private List<T> _elements;
public PriorityQueue()
{
_elements = new List<T>();
}
public PriorityQueue(int capacity)
{
_elements = new List<T>(capacity);
}
// Adds an item to the end of the list
public void Add(T item)
{
if (_elements == null)
throw new NullReferenceException("Queue is not initialized");
_elements.Add(item);
Length++;
SiftUp(Length - 1);
}
// Removes and returns the root (first) item from the list
public T Poll()
{
T output;
if (Length <= 0)
{
throw new IndexOutOfRangeException("No elements to remove");
}
if (Length == 1)
{
--Length;
output = _elements[0];
_elements.Clear();
return output;
}
output = _elements[0];
_elements[0] = _elements[--Length];
_elements.RemoveAt(Length);
SiftDown(0);
return output;
}
//Removes the first occurrence of the specified item
public void Remove(T item)
{
int removeIndex = _elements.IndexOf(item);
if (removeIndex == -1)
throw new IndexOutOfRangeException("No such element found");
Swap(removeIndex, --Length);
_elements.RemoveAt(Length);
SiftDown(removeIndex);
SiftUp(removeIndex);
}
// Returns the root (first) item from the list
public T Peek()
{
if (Length >= 1)
return _elements[0];
throw new IndexOutOfRangeException("Queue is empty");
}
// Returns true if the item is found else false
public bool Contains(T item)
{
return _elements.Contains(item);
}
// Removes all items from the list
public void Clear()
{
_elements.Clear();
}
// Swaps the position of 2 items in the list
private void Swap(int index1, int index2)
{
T temp = _elements[index1];
_elements[index1] = _elements[index2];
_elements[index2] = temp;
}
// Bubble up operation to maintain heap invariant
private void SiftUp(int index)
{
int parentIndex = index % 2 == 0 ? (index - 2) / 2 : (index - 1) / 2;
while (index >= 0 && parentIndex >= 0 && _elements[parentIndex].CompareTo(_elements[index]) >= 1)
{
Swap(index, parentIndex);
index = parentIndex;
parentIndex = index % 2 == 0 ? (index - 2) / 2 : (index - 1) / 2;
}
}
// Bubble down operation to maintain heap invariant
private void SiftDown(int index)
{
if (Length == 1)
return;
if (Length == 2)
{
if (_elements[0].CompareTo(_elements[1]) > 0)
Swap(0, 1);
return;
}
int leftChildIndex = 2 * index + 1;
int rightChildIndex = leftChildIndex + 1;
if (leftChildIndex >= Length || rightChildIndex >= Length)
return;
int childSwapIndex = _elements[leftChildIndex].CompareTo(_elements[rightChildIndex]) < 1 ? leftChildIndex : rightChildIndex;
while (leftChildIndex < Length && rightChildIndex < Length && _elements[index].CompareTo(_elements[childSwapIndex]) >= 1)
{
Swap(index, childSwapIndex);
index = childSwapIndex;
leftChildIndex = 2 * index + 1;
rightChildIndex = 2 * index + 2;
if (leftChildIndex < Length && rightChildIndex < Length)
childSwapIndex = _elements[leftChildIndex].CompareTo(_elements[rightChildIndex]) < 1 ? leftChildIndex : rightChildIndex;
else
break;
}
}
}
Online heap visualization for reference: https://www.cs.usfca.edu/~galles/visualization/Heap.html
Can someone review and provide your feedback on how this can be improved, optimized or structured better?
Sizeshouldn't have a public setter. \$\endgroup\$Size's publicity is that it can be overwritten by the consumer because of the public setter. \$\endgroup\$