W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

Heap & Priority Queue

Manage priorities efficiently with Max-Heaps and Min-Heaps.

Topics

Minutes

O(log n)

Insertion

Top-K

Best For

What is a Heap?

Access Max/Min: O(1)

Priority-Based Scheduling

Imagine an emergency room triage counter. Patients are not treated strictly in the order they arrive; instead, patients with high-severity injuries are prioritized and treated first.

A Heap is a specialized tree-based data structure that satisfies the heap ordering property, serving as the foundation for Priority Queues.

Two Main Varieties:

Max-Heap: The value of every parent node is greater than or equal to (≥) the values of its children. The absolute largest element resides at the root.
Min-Heap: The value of every parent node is less than or equal to (≤) the values of its children. The absolute smallest element resides at the root.

Structural Properties:

A heap is structured as a Complete Binary Tree—all levels are packed fully, except possibly the bottom level, which is filled from left to right. This structural constraint allows a heap to be represented efficiently as a flat, contiguous Array, mapping relationships using simple arithmetic indexes:

C++ Code — What is a Heap?

// Array Representation
// For a node at index 'i':
int parent = (i - 1) / 2;
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;

Heap Operations: Insert & Delete

Insert/Delete: O(log n)

Interactive

Loading visualizer...

Maintaining Heap Stability

When modifying a heap, we temporarily violate the ordering property. To restore it, we perform heapification:

1. Insertion (`O(log n)` Time)

Push to End: Add the new value at the very end of the array (as the bottom-rightmost leaf).
Heapify-Up (Bubble Up): Compare the new value with its parent. If it violates the heap constraint (e.g., child is larger than parent in a Max-Heap), swap them. Repeat this comparison upward until the value reaches its correct position or the root.

2. Extraction (`O(log n)` Time)

Extract Root: Take the value at the root (index 0).
Swap with Last Leaf: Move the last element of the array to the root position.
Heapify-Down (Sink Down): Compare the new root with its children. Swap it with the larger child (in a Max-Heap) or smaller child (in a Min-Heap) to maintain the heap property. Repeat this process down the tree.

C++ Code — Heap Operations: Insert & Delete

void push(int val) {
    heap.push_back(val);
    int i = heap.size() - 1;
    while(i > 0) {
        int p = (i - 1) / 2;
        if(heap[p] < heap[i]) {
            swap(heap[p], heap[i]);
            i = p;
        } else break; 
    }
}

Priority Queue in C++ STL

All Library Ops: O(log n)

Interactive

Loading visualizer...

STL Container Adapters

The C++ Standard Template Library provides a built-in container adapter, std::priority_queue, configured as a heap:

Syntax Details:

Max-Heap (Default): priority_queue<int> pq;
Min-Heap: Uses a vector container and a greater-than comparator: priority_queue<int, vector<int>, greater<int>> min_pq;

Essential Member Functions:

push(val): Inserts an item into the priority queue (O(log n)).
pop(): Removes the top item (O(log n)).
top(): Returns a reference to the top item (O(1)).

C++ Code — Priority Queue in C++ STL

#include <queue>
using namespace std;

int main() {
    // Max Heap
    priority_queue<int> pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);
    
    cout << pq.top(); // 30
    pq.pop();         // Removes 30
    
    // Min Heap
    priority_queue<int, vector<int>, greater<int>> min_pq;
    min_pq.push(10);
    min_pq.push(30);
    
    cout << min_pq.top(); // 10
}

Heap Sort

Time: O(n log n) | Space: O(1)

In-Place Sorting Algorithm

Heap Sort is a comparison-based sorting algorithm that operates directly on the input array, avoiding extra memory allocations:

How It Works:

Build Heap: Rearrange the input array into a Max-Heap (takes O(n) time using bottom-up heapification).
Sort Array: Repeatedly swap the root element (the largest value) with the last element of the active heap, decrement the heap size, and run heapify-down on the new root.

Pros and Cons:

Pros: Runs in guaranteed O(n log n) time in the best, average, and worst cases, and sorts in-place using O(1) auxiliary space.
Cons: Not a stable sorting algorithm (can reorder equal elements), and generally runs slower in practice than QuickSort due to poor cache locality (jumping indices).

C++ Code — Heap Sort

void heapSort(vector<int>& arr) {
    // 1. Build Heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
  
    // 2. Extract elements
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]); // Move current root to end
        heapify(arr, i, 0);   // Fix reduced heap
    }
}

Top-K Pattern Problems

Time: O(n log K)

Resolving Partial Sort Problems

Heaps are the optimal data structure for solving problems that ask for the "Top K" largest or smallest elements:

1. Finding the K Largest Elements (`O(n log K)` Time)

Build a Min-Heap of size K.
Iterate through the array. For each element, push it into the heap. If the heap size exceeds K, pop the smallest element.
Why Min-Heap? By popping the smallest elements, only the K largest elements remain in the heap.

2. Finding the K Smallest Elements (`O(n log K)` Time)

Build a Max-Heap of size K.
If the heap size exceeds K, pop the largest element. This discards larger values, keeping only the K smallest elements.

C++ Code — Top-K Pattern Problems

// K Largest Elements
priority_queue<int, vector<int>, greater<int>> minHeap;

for(int num : nums) {
    minHeap.push(num);
    if(minHeap.size() > k) {
        minHeap.pop(); // Remove smallest
    }
}
// Heap now has K largest

void push(int val) { heap.push_back(val); int i = heap.size() - 1; while(i > 0) { int p = (i - 1) / 2; if(heap[p] < heap[i]) { swap(heap[p], heap[i]); i = p; } else break; } }

#include <queue> using namespace std; int main() { // Max Heap priority_queue<int> pq; pq.push(10); pq.push(30); pq.push(20); cout << pq.top(); // 30 pq.pop(); // Removes 30 // Min Heap priority_queue<int, vector<int>, greater<int>> min_pq; min_pq.push(10); min_pq.push(30); cout << min_pq.top(); // 10 }

void heapSort(vector<int>& arr) { // 1. Build Heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 2. Extract elements for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); // Move current root to end heapify(arr, i, 0); // Fix reduced heap } }

// K Largest Elements priority_queue<int, vector<int>, greater<int>> minHeap; for(int num : nums) { minHeap.push(num); if(minHeap.size() > k) { minHeap.pop(); // Remove smallest } } // Heap now has K largest

Heap & Priority Queue

What is a Heap?

Priority-Based Scheduling

Two Main Varieties:

Structural Properties:

Heap Operations: Insert & Delete

Maintaining Heap Stability

1. Insertion (O(log n) Time)

2. Extraction (O(log n) Time)

Priority Queue in C++ STL

STL Container Adapters

Syntax Details:

Essential Member Functions:

Heap Sort

In-Place Sorting Algorithm

How It Works:

Pros and Cons:

Top-K Pattern Problems

Resolving Partial Sort Problems

1. Finding the K Largest Elements (O(n log K) Time)

2. Finding the K Smallest Elements (O(n log K) Time)

Heap & Priority Queue

What is a Heap?

Priority-Based Scheduling

Two Main Varieties:

Structural Properties:

Heap Operations: Insert & Delete

Maintaining Heap Stability

1. Insertion (O(log n) Time)

2. Extraction (O(log n) Time)

Priority Queue in C++ STL

STL Container Adapters

Syntax Details:

Essential Member Functions:

Heap Sort

In-Place Sorting Algorithm

How It Works:

Pros and Cons:

Top-K Pattern Problems

Resolving Partial Sort Problems

1. Finding the K Largest Elements (O(n log K) Time)

2. Finding the K Smallest Elements (O(n log K) Time)

1. Insertion (`O(log n)` Time)

2. Extraction (`O(log n)` Time)

1. Finding the K Largest Elements (`O(n log K)` Time)

2. Finding the K Smallest Elements (`O(n log K)` Time)

1. Insertion (`O(log n)` Time)

2. Extraction (`O(log n)` Time)

1. Finding the K Largest Elements (`O(n log K)` Time)

2. Finding the K Smallest Elements (`O(n log K)` Time)