Priority Queue & Binary Heap

Introduction

A Priority Queue is an extension of a normal Queue. In a standard Queue (FIFO - First In First Out), the “next” item is always the one that arrived earliest. However, in a Priority Queue, the “next” item is the one with the highest priority.

Think of a hospital emergency room:

• Queue: Patients are treated in the order they walked in.
• Priority Queue: A patient with a heart attack is treated before someone with a sprained ankle, even if the heart attack patient arrived later.

The Binary Heap

While a Priority Queue is an Abstract Data Type (ADT)—meaning it defines behavior—a Binary Heap is the most common Data Structure used to implement it efficiently.

A Binary Heap is a Binary Tree with two specific properties:

1. Shape Property: It is a Complete Binary Tree. All levels are fully filled except possibly the last level, which is filled from left to right. This allows us to store it efficiently in an Array.
2. Heap Property:
   • Min Heap: The value of each node is $\le$ the values of its children. The root is the minimum element.
   • Max Heap: The value of each node is $\ge$ the values of its children. The root is the maximum element.

Array Representation

Because of the “Complete Tree” property, we don’t need point-and-node classes. We can map the tree directly to an index-based array which is cache-friendly.

Given a node at index i:

• Parent: $\lfloor \frac{i-1}{2} \rfloor$
• Left Child: $2i + 1$
• Right Child: $2i + 2$

Core Operations

The magic of the Heap lies in how it maintains the Heap Property efficiently during modification. Operations typically take $O(\log N)$ time, which is the height of the tree.

1. Insert (Push) - “Bubble Up”

When we add a new element:

1. Place the new element at the end of the array (the first empty spot in the tree).
2. Compare it with its Parent.
3. If it violates the heap property (e.g., in a MinHeap, it’s smaller than the parent), swap them.
4. Repeat step 2-3 until the property is restored or the root is reached.

2. Extract Min/Max (Pop) - “Bubble Down”

When we remove the root (the highest priority item):

1. Replace the root with the last element in the array.
2. Remove the last element.
3. Compare the new root with its Children.
4. Swap it with the smaller/larger child (depending on Min/Max heap type).
5. Repeat until the property is restored or a leaf is reached.

Complexity Analysis

Operation	Array (Unsorted)	Array (Sorted)	Binary Heap
Peek (Get Top)	$O(N)$	$O(1)$	$O(1)$
Insert	$O(1)$	$O(N)$ (shift items)	$O(\log N)$
Extract	$O(N)$ (find max)	$O(N)$ (shift items)	$O(\log N)$

The Heap provides the best balance. It’s not as fast as a sorted array for peeking, but insertion and deletion are strictly logarithmic, making it scalable for millions of items.

C# Implementation

Here is a clean implementation of a Min-Heap in C#.

using System;
using System.Collections.Generic;

public class MinHeap<T> where T : IComparable<T>
{
    private List<T> elements = new List<T>();

    public int Count => elements.Count;

    public void Push(T item)
    {
        elements.Add(item);
        BubbleUp(elements.Count - 1);
    }

    public T Pop()
    {
        if (elements.Count == 0) throw new InvalidOperationException("Heap is empty");
        
        T result = elements[0];
        // Move last item to root
        elements[0] = elements[elements.Count - 1];
        elements.RemoveAt(elements.Count - 1);
        
        if (elements.Count > 0)
            BubbleDown(0);
            
        return result;
    }

    private void BubbleUp(int index)
    {
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
            if (elements[index].CompareTo(elements[parentIndex]) >= 0)
                break;

            Swap(index, parentIndex);
            index = parentIndex;
        }
    }

    private void BubbleDown(int index)
    {
        while (true)
        {
            int childIndex = 2 * index + 1;
            if (childIndex >= elements.Count) break;

            // Find smaller child
            int rightChild = childIndex + 1;
            if (rightChild < elements.Count && 
                elements[rightChild].CompareTo(elements[childIndex]) < 0)
            {
                childIndex = rightChild;
            }

            if (elements[index].CompareTo(elements[childIndex]) <= 0)
                break;

            Swap(index, childIndex);
            index = childIndex;
        }
    }

    private void Swap(int i, int j)
    {
        T temp = elements[i];
        elements[i] = elements[j];
        elements[j] = temp;
    }
}

Modern .NET 6+ Note

If you are using .NET 6 or later (which you likely are for modern development), you no longer need to roll your own class! C# now includes a built-in System.Collections.Generic.PriorityQueue<TElement, TPriority>.

// Example using built-in .NET 6 PriorityQueue
var pq = new PriorityQueue<string, int>();

pq.Enqueue("Low Priority Task", 10);
pq.Enqueue("Critical Task", 1);
pq.Enqueue("Medium Task", 5);

while (pq.TryDequeue(out string item, out int priority))
{
    Console.WriteLine($"Processing {item} (Priority: {priority})");
}
// Output: 
// Processing Critical Task (Priority: 1)
// Processing Medium Task (Priority: 5)
// Processing Low Priority Task (Priority: 10)

Applications

1. Graph Algorithms:
   • Dijkstra’s Algorithm: Finds the shortest path in a weighted graph. It always explores the “closest” node next, which is efficiently retrieved using a Min-Heap.
   • Prim’s Algorithm: Used for Minimum Spanning Trees.
2. Geometry Processing:
   • Visvalingam-Whyatt: As mentioned in my Visvalingam-Whyatt post, we process triangles with the smallest area first.
   • Sweepline Algorithms: Processing events (intersections, start/end points) in order of their X-coordinate.
3. Systems:
   • Task Scheduling: CPU scheduling processes based on priority levels.

Reference

• GeeksForGeeks: Binary Heap