Heap and Priority Queue

Binary heap is a tree data structure which satisfies the properties of complete binary tree. This means that every level of the tree except the last one should be filled and the nodes are as far left as possible. The two types of heaps are min and max heap. Min heap is when the the root is smaller than it’s child nodes and the root is smallest among all other nodes. Max heap is when the root is greater than it’s child nodes and the root is the largest among all other nodes. This is recursively true for all nodes.

Min Heap

Max Heap

The properties of heap described above makes it easy to be implemented with an array data structure and most commonly the heap is implemented with an array data structure. Let’s see how we would show a min heap with an array.

Based on the above representation we can define several formulas in order to detect parent or child nodes of a given node based on the index of an array. Given n is the index of an array then:

Parent node index = (n – 1) / 2

Example: Take 5th index which is 32, so (5 – 1) / 2 = 2 which is 30 the parent node.

Left child index = (2 * n) + 1

Example: Take 2nd index which is 30, so (2 * 2) + 1 = 5 which is 32 the left child.

Right child index = (2 * n) + 2

Example: Take 2nd index which is 30, so (2 * 2) + 2 = 6 which is 52 the right child.

Heap an priority queue operations

Heapify

Heapifying is an operation which rearranges the elements of the heap so it satisfies the conditions of min or max heap based on the heap type. This operation is performed after adding or removing a node from the heap or/and priority queue although in priority queue we have only enqueue and dequeue based on the priority of the elements compared to regular queue.

This operation starts from first index of non-leaf node whose index is given by n / 2 – 1 where n is the size of the array. Each root, left child and right child is compared and if they don’t satisfy the heap property the nodes are swapped. The operation is repeated until we reach the root node with index 0. Let’s see with example how we will heapify a tree which does not satisfy min heap properties.

Add/Enqueue item

When we add item to the heap/priority queue we add it as last item to the tree and then we heapify the tree as described above.

Remove/Dequeue item

When we dequeue / remove item from the tree we swap the item to be removed with the last item in the tree, the rightmost node. Then we remove the last item which became the item we wanted to remove after we made a swap in previous step. Finally we heapify the tree in order to satisfy the heap properties.

Implementation

Let’s see how we can implement priority queue in C#. First we will define an enum which will define the queue type.

    public enum PriroityQueueType
    {
        Min,
        Max
    }

Then we will define a PriorityQueue class and implement it’s methods.

    public class PriorityQueue<T> where T : IComparable<T>
    {
        private List<T> items;
        private PriroityQueueType PriroityQueueType;

        public PriorityQueue(PriroityQueueType priroityQueueType)
        {
            this.items = new List<T>();
            this.PriroityQueueType = priroityQueueType;
        }
     }

We use generic class where the type should implement IComparable in order to compare the items when we implement priority queue operations. Next let’s implement heapify method.

        private void Heapify(int index)
        {
            int count = items.Count;
            int largestOrSmallest = index;
            int leftIndex = 2 * index + 1;
            int rightIndex = 2 * index + 2;

  //check if current node is larger or smaller than left child based on the queue type
  //if true then assign left child index to variable largestOrSmallest in order to track it
            if (leftIndex < count &&
                ((PriroityQueueType == PriroityQueueType.Min 
                    && items[largestOrSmallest].CompareTo(items[leftIndex]) > 0)
                || (PriroityQueueType == PriroityQueueType.Max 
                    && items[largestOrSmallest].CompareTo(items[leftIndex]) < 0)))
            {
                largestOrSmallest = leftIndex;
            }

  //check if largestOrSmallest node is larger or smaller than right child based on the queue type
 //if true then assign right child index to variable largestOrSmallest in order to track it
            if (rightIndex < count &&
                ((PriroityQueueType == PriroityQueueType.Min 
                    && items[largestOrSmallest].CompareTo(items[rightIndex]) > 0)
                || (PriroityQueueType == PriroityQueueType.Max 
                    && items[largestOrSmallest].CompareTo(items[rightIndex]) < 0)))
            {
                largestOrSmallest = rightIndex;
            }

 //if one of the child is larger or smaller than the root then we need to swap them
            if (largestOrSmallest != index)
            {
                T temp = items[largestOrSmallest];
                items[largestOrSmallest] = items[index];
                items[index] = temp;

 //As we swapped the root item with one of the children we need to recrsively heapify the subtrees
                Heapify(largestOrSmallest);
            }
        }

Heapify method is the code representation of the heapify operation visually described above.

Next we will implement enqueue method where we add an item to the end of the queue and then we start heapifying the tree starting from index n/2-1 where n is the count of the elements in the queue.

        public void Enqueue(T item)
        {
            if (items.Count == 0)
            {
                items.Add(item);
            }
            else
            {
                items.Add(item);
                for (int i = items.Count / 2 - 1; i >= 0; i--)
                {
                    Heapify(i);
                }
            }
        }

We will implement helper method DeleteNode which will delete a node from the heap by given index of the element. We will afterwards use this method to easily implement Dequeue operation of priority queue. Delete method follows the visual steps described earlier in this article.

        private void DeleteNode(int index)
        {
            if(index > items.Count-1) throw new IndexOutOfRangeException();

            T temp = items[index];
            items[index] = items[items.Count - 1];
            items[items.Count - 1] = temp;

            items.RemoveAt(items.Count - 1);

            for (int i = items.Count / 2 - 1; i >= 0; i--)
            {
                Heapify(i);
            }
        }

Using this method to implement dequeue operation is really easy we just call it with index 0 which is the top item of the queue.

        public T Dequeue()
        {
            if (items.Count == 0) 
                throw new InvalidOperationException("The priority queue is empty");

            T topItem = items[0];

            DeleteNode(0);

            return topItem;
        }

Finally we implement Peek which is just returning the top item.

        public T Peek()
        {
            T topItem = items[0];
            return topItem;
        }

It is worth mentioning the algorithm complexity of binary heap and priority queue.

Peek – O(1)

Enqueue – O(log n)

Dequeue – O(log n)

With this we conclude the explanation of heap and priority queue.

You can read more about this topic here:
https://www.geeksforgeeks.org/priority-queue-set-1-introduction/
https://www.programiz.com/dsa/priority-queue

Advertisement