2
\$\begingroup\$

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?

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Just a small remark: I think Size shouldn't have a public setter. \$\endgroup\$
    – SomeBody
    Aug 4, 2021 at 6:36
  • \$\begingroup\$ Why do you repeat the methods' name in the comments? \$\endgroup\$ Aug 4, 2021 at 7:14
  • \$\begingroup\$ @SomeBody Actually I should rename it to Length or Count. It can be used to get the current size of the queue. I should remove the 'Capacity' as it is initialized by constructor to keep the dynamic resizing of the List restricted. \$\endgroup\$ Aug 4, 2021 at 7:35
  • 1
    \$\begingroup\$ @SouvikGhosh The problem with Size's publicity is that it can be overwritten by the consumer because of the public setter. \$\endgroup\$ Aug 4, 2021 at 7:44
  • 2
    \$\begingroup\$ Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. \$\endgroup\$
    – pacmaninbw
    Aug 4, 2021 at 13:13

1 Answer 1

3
\$\begingroup\$
public int Length { get; private set; }

_elements carries the length already, and duplicate state that you keep in sync manually is a good way to create bugs. Consider implementing the getter as returning _elements.Count, and not having a setter. That way it is impossible for the length to ever be wrong, instead of it being possible but hopefully avoided through careful coding. It will also save some small snippets of code where you update the Length.

if (_elements == null)
    throw new NullReferenceException("Queue is not initialized");

There is no legitimate way to create an uninitialized instance (or initialized, but nulled out afterwards) of this queue, so this is testing for a case that is highly unusual (created intentionally via unsafe code, reflection, etc). The method will fail safely if _elements is null anyway (ie it doesn't do any damage before automatically throwing an NRE due to accessing the list). So I deem this unnecessary.

int parentIndex = index % 2 == 0 ? (index - 2) / 2 : (index - 1) / 2;

You don't need to test whether index is even, the parent index is always (index − 1) ∕ 2. When index is even, index - 1 is odd, and the division rounds down.

    if (Length == 1)
        return;
    if (Length == 2)
    {
        if (_elements[0].CompareTo(_elements[1]) > 0)
            Swap(0, 1);
        return;
    }

This looks unnecessary. They're "fast paths" that skip a bunch of extra work in some cases, but those cases should be rare and unimportant: a priority queue that is almost empty is fast anyway regardless of such tricks, and the case of calling SiftDown on a big queue should be more common (because big queues will probably have more items removed from them). These fast path are actually slowing down the common case. But by how much, well probably not a lot.. try it.

    if (leftChildIndex >= Length || rightChildIndex >= Length)
        return;

This is a bug. If the right child does not exist, the left child could still exist, and may need to swapped with the current node to restore the heap property. The while loop has the same bug. As a trick, you may set the indexes of the left and right child equal when only the left child exists, that way the code for the case of two children can handle that case as well, without needing a whole special case for it.

For an example of it breaking:

PriorityQueue<int> P = new PriorityQueue<int>();
P.Add(0);
P.Add(1);
P.Add(2);
P.Add(3);
P.Add(4);
P.Poll();

Now inspect the elements, they are { 1, 4, 2, 3 } which is wrong, because it has 3 as a child of 4, which violates the heap property. I could not quickly find a sequence of actions where elements are polled in the wrong order, but it seems dangerous to rely on it never happening, given that the internal structure of the heap has been corrupted.

By the way there is also a fundamentally different alternative way to implement both sift down and sift up that does approximately half the data movement. What both of them really do is take some non-contiguous subset of elements and "shift" them all by one place . That can be done by remembering one element, leaving a "hole" in the list, then instead of swapping you always write an element into the "hole" (which costs only 1 read and 1 write, instead of 2 of each that a swap would cost). Then at the end, you drop the remembered element into the final position of the hole. That would be especially relevant if T is a sizable struct.

\$\endgroup\$
1
  • \$\begingroup\$ Good points, +1. Updated the code with the fixes. \$\endgroup\$ Aug 4, 2021 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.