Heap & Priority Queue

Heaps and priority queues are fundamental data structures that maintain the highest (max-heap) or lowest (min-heap) priority element at the root, enabling efficient retrieval and insertion operations. This section explores binary heaps, priority queue implementations, and common algorithmic patterns for solving priority-based problems.

Heaps and priority queues are essential tools for efficiently managing elements based on their priority. They transform complex priority-based problems from O(N²) nested loops into O(N log N) operations, making them indispensable for coding interviews and real-world applications.

Real-World Analogy

Think of a priority queue like a hospital emergency room. Patients with the most critical conditions (highest priority) are treated first, regardless of when they arrived. The triage nurse (the heap) constantly maintains this priority order, ensuring the most urgent cases are always at the front.

Visual Explanation

A binary heap is a complete binary tree where each parent node satisfies the heap property:

Max-Heap Property: Parent >= Children

        100
       /    \
     80      60
    /  \    /  \
   40  30  20  10

Min-Heap Property: Parent <= Children

        10
       /    \
     20      30
    /  \    /  \
   40  60  80  100

The heap is stored as an array where:

• Parent of index i: Math.floor((i-1)/2)
• Left child of index i: 2*i + 1
• Right child of index i: 2*i + 2

When to Use This Pattern

Use heap and priority queue patterns when you encounter these problem characteristics:

• Need to find the k largest or smallest elements efficiently
• Processing elements in priority order (highest/lowest first)
• Maintaining a running median of streaming data
• Merging k sorted lists or arrays
• Implementing scheduling algorithms with priorities
• Finding shortest paths in graphs (Dijkstra’s algorithm)
• Need O(log n) insertion and extraction operations
• Space complexity must be O(n) or better

Complexity Analysis

Common Mistakes

1. Wrong heap type: Using min-heap when max-heap is needed (or vice versa)
2. Incorrect indexing: Off-by-one errors in parent/child calculations
3. Missing heap property restoration: Forgetting to bubble up after insertion or sink down after extraction
4. Comparator errors: Incorrect priority ordering in custom comparators
5. Memory waste: Using linked lists instead of arrays for heap storage

Next Steps

Ready to dive deeper? Check out our Code Templates for multi-language implementations and Practice Problems to apply these concepts to real coding challenges.