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)

A Heap is a specialized binary tree-based data structure that satisfies the heap property. It is essentially a widely used implementation of a Priority Queue.

Two Main Types:
1. Max-Heap: The value of each node is greater than or equal to the values of its children. The largest element is at the root.
2. Min-Heap: The value of each node is less than or equal to the values of its children. The smallest element is at the root.

Key Property:
A Heap is always a Complete Binary Tree. This means all levels are filled completely except possibly the last level, which is filled from left to right.
This allows heaps to be efficiently stored in an Array!

C++ Code

// 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...

1. Insertion (Heapify Up):
- Add the new element at the end of the array.
- Compare it with its parent.
- If it violates the heap property (e.g., child > parent in Max-Heap), swap them.
- Repeat until the property is restored.
- Time Check: O(log n) because height of tree is log n.

2. Deletion / Extract Max (Heapify Down):
- Remove the root element (max).
- Move the last element of the heap to the root.
- Compare the new root with its children.
- Swap with the larger child if heap property is violated.
- Repeat down the tree.
- Time Check: O(log n).

C++ Code

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...

In C++, std::priority_queue is the standard implementation of a heap.

Default Behavior:
By default, it is a Max-Heap.
priority_queue pq;

Min-Heap Syntax:
To make it a Min-Heap, we use a custom comparator:
priority_queue, greater> min_pq;

Common Operations:
- push(val): Inserts an element.
- pop(): Removes the top element.
- top(): Returns the top element (Max or Min).
- empty(): Checks if empty.

C++ Code

#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)

Heap Sort is an efficient comparison-based sorting algorithm.

Algorithm:
1. Build a Max-Heap from the input array.
2. At this point, the largest item is at the root.
3. Replace it with the last item of the heap followed by reducing the size of heap by 1.
4. Heapify the root of the tree.
5. Repeat steps 2-4 while size of heap is greater than 1.

Pros:
- ✅ O(n log n) time complexity (Best, Average, Worst).
- ✅ O(1) Space Complexity (In-place sort).
- ✅ Does not suffer from QuickSort's O(n²) worst case.

Cons:
- ❌ Not a stable sort.
- ❌ Slower in practice than QuickSort due to poor cache locality (jumping indices).

C++ Code

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)

Heaps are the go-to structure for "Top K" type problems.

1. K Largest Elements:
- Use a Min-Heap of size K.
- Push elements. If size > K, pop the smallest.
- Remaining elements are the K largest.
- Why Min-Heap? Because we want to "discard" the smaller elements to keep the largest ones.

2. K Smallest Elements:
- Use a Max-Heap of size K.
- Push elements. If size > K, pop the largest.
- Remaining elements are the K smallest.

3. Merge K Sorted Lists:
- Use a Min-Heap.
- Insert first element of all K lists.
- Extract min, and insert the next element from that list.

C++ Code

// 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