Understanding Priority Queue (Min-Heap)

Priority queues are usually implemented using heaps, but I wanted to understand how heaps actually work under the hood. So I decided to build a min-heap from scratch. Implementing it myself really helped me understand why heaps are so efficient for priority queues.

What Is a Min-Heap?

A min-heap is a binary tree where:

• The parent is always smaller than or equal to its children
• The root is the smallest element
• It's a complete binary tree (filled left to right)

This structure lets me get the minimum element in O(1) and remove it in O(log n).

Why I Wanted to Understand It

I was using priority queues in my code but didn't understand how they worked internally. I felt like I was using a black box. So I decided to implement one myself.

My Min-Heap Implementation

I implemented it using an array (which is how heaps are typically stored):

class MinHeap {
    constructor() {
        this.heap = [];
    }

    // Helper methods to navigate the tree
    getParentIndex(i) { 
        return Math.floor((i - 1) / 2); 
    }
    
    getLeftChildIndex(i) { 
        return 2 * i + 1; 
    }
    
    getRightChildIndex(i) { 
        return 2 * i + 2; 
    }

    // Add element to heap
    add(value) {
        this.heap.push(value);
        this.heapifyUp(); // Maintain heap property
    }

    // Remove and return minimum element
    poll() {
        if (this.heap.length === 1) {
            return this.heap.pop();
        }

        const root = this.heap[0];
        this.heap[0] = this.heap.pop(); // Move last element to root
        this.heapifyDown(); // Maintain heap property
        return root;
    }

    // Move element up to maintain heap property
    heapifyUp() {
        let index = this.heap.length - 1;
        
        while (index > 0) {
            const parentIndex = this.getParentIndex(index);
            
            // If parent is smaller or equal, we're done
            if (this.heap[parentIndex] <= this.heap[index]) {
                break;
            }
            
            // Swap with parent
            [this.heap[index], this.heap[parentIndex]] = 
            [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    // Move element down to maintain heap property
    heapifyDown() {
        let index = 0;
        
        while (this.getLeftChildIndex(index) < this.heap.length) {
            const leftIndex = this.getLeftChildIndex(index);
            const rightIndex = this.getRightChildIndex(index);
            let smallerChildIndex = leftIndex;

            // Find smaller child
            if (rightIndex < this.heap.length && 
                this.heap[rightIndex] < this.heap[leftIndex]) {
                smallerChildIndex = rightIndex;
            }

            // If current is smaller than both children, we're done
            if (this.heap[index] <= this.heap[smallerChildIndex]) {
                break;
            }

            // Swap with smaller child
            [this.heap[index], this.heap[smallerChildIndex]] = 
            [this.heap[smallerChildIndex], this.heap[index]];
            index = smallerChildIndex;
        }
    }

    isEmpty() {
        return this.heap.length === 0;
    }
}

How It Works

Adding an element:

1. Add to the end of the array
2. "Bubble up" by comparing with parent
3. Swap if parent is larger
4. Repeat until heap property is restored

Removing minimum:

1. Remove root (minimum)
2. Move last element to root
3. "Bubble down" by comparing with children
4. Swap with smaller child if needed
5. Repeat until heap property is restored

Testing It

const minHeap = new MinHeap();
minHeap.add(10);
minHeap.add(5);
minHeap.add(20);
minHeap.add(1);

while (!minHeap.isEmpty()) {
    console.log(minHeap.poll()); // Prints: 1, 5, 10, 20
}

Java's Built-in PriorityQueue

In Java, I can use the built-in PriorityQueue, which is a min-heap by default:

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        minHeap.add(10);
        minHeap.add(5);
        minHeap.add(20);
        minHeap.add(1);
        
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll()); // Prints: 1, 5, 10, 20
        }
    }
}

What I Learned

Implementing a heap from scratch taught me:

• How the array representation works (parent at i, children at 2i+1 and 2i+2)
• Why heapify operations are O(log n)
• How the heap property is maintained
• Why heaps are perfect for priority queues

Key Takeaways

• Min-heaps keep the minimum at the root
• Array representation is efficient (no pointers needed)
• Heapify operations maintain the heap property
• O(log n) insert and remove, O(1) peek at minimum

Understanding how heaps work internally really helped me appreciate why priority queues are so efficient. It's one of those data structures where the implementation is elegant and the performance is great. I hope this helps you understand heaps better too!