Heaps in DSA: Priority Queues & Heap Algorithms

1. Heap Fundamentals

Min-Heap

Definition

Min-Heap is a complete binary tree where the value of each node is less than or equal to the values of its children. The smallest element is always at the root, making it ideal for priority queues where the highest priority is the smallest value.

How It Works

1

Insert (Bubble Up)

Add new element at the end of the heap array
Compare with parent; swap if smaller
Repeat until heap property is restored

2

Extract Min (Sink Down)

Remove root (minimum element)
Move last element to root
Compare with children; swap with smallest child
Repeat until heap property is restored

3

Array Representation

Parent: (i-1)/2
Left Child: 2i+1
Right Child: 2i+2

class MinHeap:
    def __init__(self):
        self.heap = []
    
    def insert(self, value):
        self.heap.append(value)
        self._bubble_up(len(self.heap) - 1)
    
    def extract_min(self):
        if not self.heap:
            raise Exception("Heap is empty")
        min_val = self.heap[0]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self._sink_down(0)
        return min_val
    
    def _bubble_up(self, index):
        while index > 0:
            parent = (index - 1) // 2
            if self.heap[parent] <= self.heap[index]:
                break
            self.heap[parent], self.heap[index] = self.heap[index], self.heap[parent]
            index = parent
    
    def _sink_down(self, index):
        smallest = index
        left = 2 * index + 1
        right = 2 * index + 2
        
        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        
        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._sink_down(smallest)
    
    def peek(self):
        return self.heap[0] if self.heap else None
    
    def size(self):
        return len(self.heap)

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    insert(value) {
        this.heap.push(value);
        this.bubbleUp(this.heap.length - 1);
    }
    
    extractMin() {
        if (this.isEmpty()) throw new Error("Heap is empty");
        const min = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.sinkDown(0);
        }
        return min;
    }
    
    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] <= this.heap[index]) break;
            [this.heap[parentIndex], this.heap[index]] = 
                [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }
    
    sinkDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let smallest = index;
        
        if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
            smallest = left;
        }
        if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
            smallest = right;
        }
        
        if (smallest !== index) {
            [this.heap[index], this.heap[smallest]] = 
                [this.heap[smallest], this.heap[index]];
            this.sinkDown(smallest);
        }
    }
    
    peek() { return this.heap[0]; }
    isEmpty() { return this.heap.length === 0; }
}

import java.util.ArrayList;
import java.util.List;

public class MinHeap {
    private List<Integer> heap;
    
    public MinHeap() {
        heap = new ArrayList<>();
    }
    
    public void insert(int value) {
        heap.add(value);
        bubbleUp(heap.size() - 1);
    }
    
    public int extractMin() {
        if (heap.isEmpty()) throw new RuntimeException("Heap is empty");
        int min = heap.get(0);
        int last = heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) {
            heap.set(0, last);
            sinkDown(0);
        }
        return min;
    }
    
    private void bubbleUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap.get(parent) <= heap.get(index)) break;
            swap(parent, index);
            index = parent;
        }
    }
    
    private void sinkDown(int index) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < heap.size() && heap.get(left) < heap.get(smallest))
            smallest = left;
        if (right < heap.size() && heap.get(right) < heap.get(smallest))
            smallest = right;
        
        if (smallest != index) {
            swap(index, smallest);
            sinkDown(smallest);
        }
    }
    
    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
    
    public int peek() { return heap.get(0); }
    public int size() { return heap.size(); }
}

#include <vector>
#include <stdexcept>
using namespace std;

class MinHeap {
private:
    vector<int> heap;
    
    void bubbleUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[parent] <= heap[index]) break;
            swap(heap[parent], heap[index]);
            index = parent;
        }
    }
    
    void sinkDown(int index) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < heap.size() && heap[left] < heap[smallest])
            smallest = left;
        if (right < heap.size() && heap[right] < heap[smallest])
            smallest = right;
        
        if (smallest != index) {
            swap(heap[index], heap[smallest]);
            sinkDown(smallest);
        }
    }
    
public:
    void insert(int value) {
        heap.push_back(value);
        bubbleUp(heap.size() - 1);
    }
    
    int extractMin() {
        if (heap.empty()) throw runtime_error("Heap is empty");
        int minVal = heap[0];
        int last = heap.back();
        heap.pop_back();
        if (!heap.empty()) {
            heap[0] = last;
            sinkDown(0);
        }
        return minVal;
    }
    
    int peek() { return heap[0]; }
    int size() { return heap.size(); }
    bool empty() { return heap.empty(); }
};

Complexity: Insert O(log n), Extract O(log n), Peek O(1)
Use When: Need quick access to minimum element

Max-Heap

Definition

Max-Heap is a complete binary tree where the value of each node is greater than or equal to the values of its children. The largest element is always at the root, making it ideal for problems requiring the maximum element.

How It Works

1

Insert (Bubble Up)

Add new element at the end
Compare with parent; swap if larger
Repeat until heap property restored

2

Extract Max (Sink Down)

Remove root (maximum element)
Move last element to root
Compare with children; swap with largest child
Repeat until heap property restored

class MaxHeap:
    def __init__(self):
        self.heap = []
    
    def insert(self, value):
        self.heap.append(value)
        self._bubble_up(len(self.heap) - 1)
    
    def extract_max(self):
        if not self.heap:
            raise Exception("Heap is empty")
        max_val = self.heap[0]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self._sink_down(0)
        return max_val
    
    def _bubble_up(self, index):
        while index > 0:
            parent = (index - 1) // 2
            if self.heap[parent] >= self.heap[index]:
                break
            self.heap[parent], self.heap[index] = self.heap[index], self.heap[parent]
            index = parent
    
    def _sink_down(self, index):
        largest = index
        left = 2 * index + 1
        right = 2 * index + 2
        
        if left < len(self.heap) and self.heap[left] > self.heap[largest]:
            largest = left
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right
        
        if largest != index:
            self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
            self._sink_down(largest)
    
    def peek(self):
        return self.heap[0] if self.heap else None

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    
    insert(value) {
        this.heap.push(value);
        this.bubbleUp(this.heap.length - 1);
    }
    
    extractMax() {
        if (this.isEmpty()) throw new Error("Heap is empty");
        const max = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.sinkDown(0);
        }
        return max;
    }
    
    bubbleUp(index) {
        while (index > 0) {
            const parent = Math.floor((index - 1) / 2);
            if (this.heap[parent] >= this.heap[index]) break;
            [this.heap[parent], this.heap[index]] = 
                [this.heap[index], this.heap[parent]];
            index = parent;
        }
    }
    
    sinkDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let largest = index;
        
        if (left < this.heap.length && this.heap[left] > this.heap[largest])
            largest = left;
        if (right < this.heap.length && this.heap[right] > this.heap[largest])
            largest = right;
        
        if (largest !== index) {
            [this.heap[index], this.heap[largest]] = 
                [this.heap[largest], this.heap[index]];
            this.sinkDown(largest);
        }
    }
    
    peek() { return this.heap[0]; }
    isEmpty() { return this.heap.length === 0; }
}

public class MaxHeap {
    private List<Integer> heap;
    
    public MaxHeap() {
        heap = new ArrayList<>();
    }
    
    public void insert(int value) {
        heap.add(value);
        bubbleUp(heap.size() - 1);
    }
    
    public int extractMax() {
        if (heap.isEmpty()) throw new RuntimeException("Heap is empty");
        int max = heap.get(0);
        int last = heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) {
            heap.set(0, last);
            sinkDown(0);
        }
        return max;
    }
    
    private void bubbleUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap.get(parent) >= heap.get(index)) break;
            swap(parent, index);
            index = parent;
        }
    }
    
    private void sinkDown(int index) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < heap.size() && heap.get(left) > heap.get(largest))
            largest = left;
        if (right < heap.size() && heap.get(right) > heap.get(largest))
            largest = right;
        
        if (largest != index) {
            swap(index, largest);
            sinkDown(largest);
        }
    }
    
    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
    
    public int peek() { return heap.get(0); }
}

class MaxHeap {
private:
    vector<int> heap;
    
    void bubbleUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[parent] >= heap[index]) break;
            swap(heap[parent], heap[index]);
            index = parent;
        }
    }
    
    void sinkDown(int index) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < heap.size() && heap[left] > heap[largest])
            largest = left;
        if (right < heap.size() && heap[right] > heap[largest])
            largest = right;
        
        if (largest != index) {
            swap(heap[index], heap[largest]);
            sinkDown(largest);
        }
    }
    
public:
    void insert(int value) {
        heap.push_back(value);
        bubbleUp(heap.size() - 1);
    }
    
    int extractMax() {
        if (heap.empty()) throw runtime_error("Heap is empty");
        int maxVal = heap[0];
        int last = heap.back();
        heap.pop_back();
        if (!heap.empty()) {
            heap[0] = last;
            sinkDown(0);
        }
        return maxVal;
    }
    
    int peek() { return heap[0]; }
};

2. Heap Operations & Algorithms

Heap Sort

Definition

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides the array into sorted and unsorted regions and repeatedly extracts the maximum/minimum element from the heap.

How It Works

1

Build Max Heap

Start from last non-leaf node
Heapify each node to satisfy heap property
Result: Largest element at root

2

Extract & Swap

Swap root (largest) with last element
Reduce heap size by 1
Heapify the reduced heap

3

Repeat

Continue until heap size becomes 1
Array becomes sorted in ascending order

def heap_sort(arr):
    n = len(arr)
    
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # Swap
        heapify(arr, i, 0)
    
    return arr

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

function heapSort(arr) {
    const n = arr.length;
    
    // Build max heap
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // Extract elements one by one
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, i, 0);
    }
    return arr;
}

function heapify(arr, n, i) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

public static void heapSort(int[] arr) {
    int n = arr.length;
    
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // Extract elements
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, n, largest);
    }
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // Extract elements
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

Complexity: O(n log n) time, O(1) space
Use When: In-place sorting with guaranteed O(n log n)

Top K Elements

Definition

Top K Elements problem finds the K largest or smallest elements in an array using a min-heap or max-heap. This approach is optimal for large datasets.

How It Works

1

Initialize Min-Heap

Create min-heap of size K
Insert first K elements

2

Process Remaining

For each element, compare with heap root
If larger than root, remove root and insert element

3

Extract Result

Heap contains K largest elements
Elements remain in heap order

import heapq

def top_k_elements(nums, k):
    min_heap = []
    
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    
    return min_heap

# For Kth largest element
def kth_largest(nums, k):
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap[0]

function topKElements(nums, k) {
    const minHeap = new MinHeap();
    
    for (const num of nums) {
        minHeap.insert(num);
        if (minHeap.size() > k) {
            minHeap.extractMin();
        }
    }
    
    return minHeap.heap;
}

// Kth largest element
function kthLargest(nums, k) {
    const minHeap = new MinHeap();
    
    for (const num of nums) {
        minHeap.insert(num);
        if (minHeap.size() > k) {
            minHeap.extractMin();
        }
    }
    
    return minHeap.peek();
}

import java.util.PriorityQueue;

public static List<Integer> topKElements(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    return new ArrayList<>(minHeap);
}

public static int kthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    return minHeap.peek();
}

#include <queue>
#include <vector>
using namespace std;

vector<int> topKElements(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    return result;
}

int kthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    return minHeap.top();
}

Complexity: O(n log k) time, O(k) space
Use When: Finding top/largest K elements

3. Heapify & Heap Construction

Heapify (Build Heap)

Definition

Heapify is the process of converting an arbitrary array into a heap in O(n) time. It works by applying the sink-down operation on non-leaf nodes from bottom to top.

How It Works

1

Start from last non-leaf

Index = (n/2) - 1
All leaf nodes are already valid heaps

2

Apply sink-down

For each node, ensure it's >= children
Swap if needed and recurse down

3

Move upward

Continue for all indices down to 0
Result: Complete heap structure

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def build_heap(arr):
    n = len(arr)
    # Start from last non-leaf node
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    return arr

function heapify(arr, n, i) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

function buildHeap(arr) {
    const n = arr.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    return arr;
}

public static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

public static void buildHeap(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void buildHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

Complexity: O(n) time, O(log n) recursion stack
Use When: Converting array to heap efficiently

4. Real-World Applications

Priority Queue (Task Scheduler)

Task Scheduling: Operating systems use heaps to schedule processes by priority

import heapq

class TaskScheduler:
    def __init__(self):
        self.heap = []  # (priority, task)
    
    def add_task(self, task, priority):
        heapq.heappush(self.heap, (priority, task))
    
    def execute_task(self):
        if self.heap:
            priority, task = heapq.heappop(self.heap)
            return task
        return None

class PriorityQueue {
    constructor() {
        this.heap = [];
    }
    
    enqueue(task, priority) {
        this.heap.push({task, priority});
        this.bubbleUp(this.heap.length - 1);
    }
    
    dequeue() {
        if (this.isEmpty()) return null;
        const min = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.sinkDown(0);
        }
        return min.task;
    }
}

import java.util.PriorityQueue;

class Task implements Comparable<Task> {
    String name;
    int priority;
    
    Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }
    
    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }
}

class TaskScheduler {
    PriorityQueue<Task> pq = new PriorityQueue<>();
    
    void addTask(String name, int priority) {
        pq.offer(new Task(name, priority));
    }
    
    String executeTask() {
        return pq.poll().name;
    }
}

#include <queue>
#include <vector>
#include <string>

struct Task {
    string name;
    int priority;
    
    bool operator>(const Task& other) const {
        return priority > other.priority;
    }
};

class TaskScheduler {
    priority_queue<Task, vector<Task>, greater<Task>> pq;
    
public:
    void addTask(string name, int priority) {
        pq.push({name, priority});
    }
    
    string executeTask() {
        Task t = pq.top();
        pq.pop();
        return t.name;
    }
};

Dijkstra's Shortest Path

Graph Algorithms: Heaps optimize distance calculations

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_dist, node = heapq.heappop(pq)
        
        if current_dist > distances[node]:
            continue
        
        for neighbor, weight in graph[node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

function dijkstra(graph, start) {
    const distances = {};
    const pq = new MinHeap();
    
    for (const node in graph) {
        distances[node] = Infinity;
    }
    distances[start] = 0;
    pq.insert({node: start, dist: 0});
    
    while (!pq.isEmpty()) {
        const {node, currentDist} = pq.extractMin();
        if (currentDist > distances[node]) continue;
        
        for (const [neighbor, weight] of graph[node]) {
            const distance = currentDist + weight;
            if (distance < distances[neighbor]) {
                distances[neighbor] = distance;
                pq.insert({node: neighbor, dist: distance});
            }
        }
    }
    return distances;
}

import java.util.*;

class Dijkstra {
    static int[] dijkstra(Map<Integer, List<int[]>> graph, int start, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{start, 0});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int node = curr[0];
            int currentDist = curr[1];
            
            if (currentDist > dist[node]) continue;
            
            for (int[] edge : graph.get(node)) {
                int neighbor = edge[0];
                int weight = edge[1];
                int distance = currentDist + weight;
                
                if (distance < dist[neighbor]) {
                    dist[neighbor] = distance;
                    pq.offer(new int[]{neighbor, distance});
                }
            }
        }
        return dist;
    }
}

#include <queue>
#include <vector>
#include <climits>

vector<int> dijkstra(vector<vector<pair<int, int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [currentDist, node] = pq.top();
        pq.pop();
        
        if (currentDist > dist[node]) continue;
        
        for (auto [neighbor, weight] : graph[node]) {
            int distance = currentDist + weight;
            if (distance < dist[neighbor]) {
                dist[neighbor] = distance;
                pq.push({distance, neighbor});
            }
        }
    }
    return dist;
}

Median Maintenance

Two-Heap Approach: Track median in a data stream

import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []  # store smaller half (negated for max-heap)
        self.min_heap = []  # store larger half
    
    def add_num(self, num):
        heapq.heappush(self.max_heap, -num)
        heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        
        if len(self.min_heap) > len(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
    
    def find_median(self):
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        return (-self.max_heap[0] + self.min_heap[0]) / 2

class MedianFinder {
    constructor() {
        this.maxHeap = new MaxHeap();  // smaller half
        this.minHeap = new MinHeap();  // larger half
    }
    
    addNum(num) {
        this.maxHeap.insert(num);
        this.minHeap.insert(this.maxHeap.extractMax());
        
        if (this.minHeap.size() > this.maxHeap.size()) {
            this.maxHeap.insert(this.minHeap.extractMin());
        }
    }
    
    findMedian() {
        if (this.maxHeap.size() > this.minHeap.size()) {
            return this.maxHeap.peek();
        }
        return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
    }
}

class MedianFinder {
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;
    
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
        
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

class MedianFinder {
private:
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
public:
    void addNum(int num) {
        maxHeap.push(num);
        minHeap.push(maxHeap.top());
        maxHeap.pop();
        
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        }
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
};

Problem Type	Approach	Time Complexity
Kth Largest Element	Min-heap of size K	O(n log k)
Merge K Sorted Arrays	Min-heap with pointers	O(n log k)
Sliding Window Median	Two heaps (min + max)	O(n log k)
Huffman Coding	Min-heap for tree construction	O(n log n)
Dijkstra's Algorithm	Min-heap for distances	O(E log V)

Report Content

Heaps in DSA: Priority Queues & Heap Algorithms

Heap Usage in Systems (2023)

1. Heap Fundamentals

Min-Heap

Definition

How It Works

Insert (Bubble Up)

Extract Min (Sink Down)

Array Representation

Max-Heap

Definition

How It Works

Insert (Bubble Up)

Extract Max (Sink Down)

2. Heap Operations & Algorithms

Heap Sort

Definition

How It Works

Build Max Heap

Extract & Swap

Repeat

Top K Elements

Definition

How It Works

Initialize Min-Heap

Process Remaining

Extract Result

3. Heapify & Heap Construction

Heapify (Build Heap)

Definition

How It Works

Start from last non-leaf

Apply sink-down

Move upward

4. Real-World Applications

Priority Queue (Task Scheduler)

Dijkstra's Shortest Path

Median Maintenance

Heap Problem-Solving Cheat Sheet

Heap Problem-Solving Checklist

Share and Join the Discussion