Heap | Dheerendra Varma

What is a Heap?

A heap is a complete binary tree that satisfies the heap property. In a max-heap, every parent is greater than or equal to its children — so the root is always the maximum element. In a min-heap, every parent is less than or equal to its children, and the root is always the minimum.

Because the tree is complete — all levels are fully filled except possibly the last, which is filled left to right — it maps perfectly to an array. For a node at index i, its left child is at 2i + 1, its right child at 2i + 2, and its parent at (i - 1) / 2. This arithmetic indexing eliminates pointer overhead entirely.

Two fundamental operations maintain the heap property after a mutation. Sift-up (used after insert): swap the newly added element with its parent while it is larger than the parent. Sift-down (used after extracting the root): swap the promoted element with the larger of its two children while it violates the heap property.

Applications

Priority queues — the abstract data type for always retrieving the highest-priority element — are implemented with heaps. Dijkstra's shortest-path algorithm uses a min-heap to always process the closest unvisited vertex. Prim's minimum spanning tree algorithm does the same. Operating system schedulers use priority heaps for process scheduling. Heap sort extracts elements from a max-heap in O(n log n) with O(1) extra space. K-way merge and top-K queries are natural heap applications.

Representations

The array representation is the only standard representation for a heap. Every heap in production code is an array with index arithmetic.

// Max-heap index relationships
fn parent(i: usize)      -> usize { (i - 1) / 2 }
fn left_child(i: usize)  -> usize { 2 * i + 1 }
fn right_child(i: usize) -> usize { 2 * i + 2 }
 
fn show_heap_layout() {
    //       10
    //      /  \
    //     9    8
    //    / \  / \
    //   7   6 5   4
    let heap = [10, 9, 8, 7, 6, 5, 4];
    let root = heap[0];                        // 10
    let left_of_root = heap[left_child(0)];    // 9
    let right_of_root = heap[right_child(0)];  // 8
    let parent_of_6 = heap[parent(4)];         // 9  (index 4 is 6, parent is index 1)
    println!("root={root} left={left_of_root} right={right_of_root} parent_of_6={parent_of_6}");
}

Rust's standard library provides BinaryHeap<T> — a max-heap. For a min-heap, wrap elements in std::cmp::Reverse<T>.

use std::collections::BinaryHeap;
use std::cmp::Reverse;
 
fn stdlib_heap() {
    // Max-heap
    let mut max_heap = BinaryHeap::new();
    max_heap.push(3); max_heap.push(1); max_heap.push(4);
    println!("max: {:?}", max_heap.peek()); // Some(4)
    println!("pop: {:?}", max_heap.pop());  // Some(4)
 
    // Min-heap via Reverse
    let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    min_heap.push(Reverse(3)); min_heap.push(Reverse(1)); min_heap.push(Reverse(4));
    println!("min: {:?}", min_heap.peek().map(|r| r.0)); // Some(1)
}

Operations and Time Complexity

Operation	Time	Notes
peek / get_max	O(1)	Root element
push / insert	O(log n)	Sift-up from last position
pop / extract_max	O(log n)	Swap root with last, sift-down
heapify (build from array)	O(n)	Bottom-up sift-down, not O(n log n)
search	O(n)	No ordering for non-root elements
delete arbitrary	O(log n)	Decrease key to max, extract

Implementation in Rust

A complete max-heap implementation showing sift-up, sift-down, push, pop, and O(n) heapify.

struct MaxHeap {
    data: Vec<i32>,
}
 
impl MaxHeap {
    fn new() -> Self { MaxHeap { data: Vec::new() } }
 
    fn peek(&self) -> Option<i32> { self.data.first().copied() }
 
    fn push(&mut self, val: i32) {
        self.data.push(val);
        self.sift_up(self.data.len() - 1);
    }
 
    fn pop(&mut self) -> Option<i32> {
        if self.data.is_empty() { return None; }
        let n = self.data.len();
        self.data.swap(0, n - 1);
        let max = self.data.pop();
        if !self.data.is_empty() { self.sift_down(0); }
        max
    }
 
    // Build heap from unsorted Vec in O(n)
    fn heapify(data: Vec<i32>) -> Self {
        let mut h = MaxHeap { data };
        let n = h.data.len();
        // Start from last non-leaf and sift down
        for i in (0..n / 2).rev() {
            h.sift_down(i);
        }
        h
    }
 
    fn sift_up(&mut self, mut i: usize) {
        while i > 0 {
            let p = (i - 1) / 2;
            if self.data[i] > self.data[p] {
                self.data.swap(i, p);
                i = p;
            } else { break; }
        }
    }
 
    fn sift_down(&mut self, mut i: usize) {
        let n = self.data.len();
        loop {
            let mut largest = i;
            let l = 2 * i + 1;
            let r = 2 * i + 2;
            if l < n && self.data[l] > self.data[largest] { largest = l; }
            if r < n && self.data[r] > self.data[largest] { largest = r; }
            if largest == i { break; }
            self.data.swap(i, largest);
            i = largest;
        }
    }
}
 
fn main() {
    let mut h = MaxHeap::heapify(vec![3, 1, 4, 1, 5, 9, 2, 6]);
    println!("max: {:?}", h.peek()); // Some(9)
    h.push(10);
    println!("max: {:?}", h.peek()); // Some(10)
    println!("pop: {:?}", h.pop());  // Some(10)
    println!("pop: {:?}", h.pop());  // Some(9)
}

Fundamental Algorithms and Problems

K Largest Elements

Find the k largest elements in an unsorted array. The min-heap approach maintains a heap of exactly k elements. For each new element, if it is larger than the heap's minimum (the root), evict the minimum and insert the new element. After scanning all n elements, the heap contains the k largest. This runs in O(n log k) and uses only O(k) space — better than sorting when k is much smaller than n.

use std::collections::BinaryHeap;
use std::cmp::Reverse;
 
fn k_largest(arr: &[i32], k: usize) -> Vec<i32> {
    let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    for &x in arr {
        min_heap.push(Reverse(x));
        if min_heap.len() > k {
            min_heap.pop(); // remove smallest
        }
    }
    min_heap.into_iter().map(|Reverse(x)| x).collect()
}
 
fn main() {
    let arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
    let mut result = k_largest(&arr, 4);
    result.sort_unstable_by(|a, b| b.cmp(a));
    println!("{:?}", result); // [9, 6, 5, 5]
}

Kth Largest Element in a Stream

Maintain a running k-largest as elements arrive one at a time. Keep a min-heap of size k. The root of the heap is always the kth largest element seen so far.

use std::collections::BinaryHeap;
use std::cmp::Reverse;
 
struct KthLargest {
    k: usize,
    heap: BinaryHeap<Reverse<i32>>,
}
 
impl KthLargest {
    fn new(k: usize, initial: &[i32]) -> Self {
        let mut kl = KthLargest { k, heap: BinaryHeap::new() };
        for &x in initial { kl.add(x); }
        kl
    }
 
    fn add(&mut self, val: i32) -> i32 {
        self.heap.push(Reverse(val));
        if self.heap.len() > self.k { self.heap.pop(); }
        self.heap.peek().unwrap().0
    }
}
 
fn main() {
    let mut kl = KthLargest::new(3, &[4, 5, 8, 2]);
    println!("{}", kl.add(3));  // 4  (stream: 2,3,4,5,8 → 3rd largest = 4)
    println!("{}", kl.add(5));  // 5
    println!("{}", kl.add(10)); // 5
    println!("{}", kl.add(9));  // 8
}

Merge K Sorted Lists

Merge k sorted arrays into one sorted array. Insert the first element of each list into a min-heap along with the list index and element index. Repeatedly extract the minimum, add it to the result, and insert that list's next element. This runs in O(N log k) where N is the total number of elements and k is the number of lists.

use std::collections::BinaryHeap;
use std::cmp::Reverse;
 
fn merge_k_sorted(lists: &[Vec<i32>]) -> Vec<i32> {
    // (value, list_index, element_index)
    let mut heap: BinaryHeap<Reverse<(i32, usize, usize)>> = BinaryHeap::new();
    for (i, list) in lists.iter().enumerate() {
        if !list.is_empty() {
            heap.push(Reverse((list[0], i, 0)));
        }
    }
    let mut result = Vec::new();
    while let Some(Reverse((val, li, ei))) = heap.pop() {
        result.push(val);
        let next = ei + 1;
        if next < lists[li].len() {
            heap.push(Reverse((lists[li][next], li, next)));
        }
    }
    result
}
 
fn main() {
    let lists = vec![
        vec![1, 4, 7],
        vec![2, 5, 8],
        vec![3, 6, 9],
    ];
    println!("{:?}", merge_k_sorted(&lists));
    // [1, 2, 3, 4, 5, 6, 7, 8, 9]
}

Median of a Data Stream

Find the median of a stream of integers after each insertion in O(log n) time per insertion and O(1) per median query. Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep them balanced so their sizes differ by at most one. The median is either the root of the larger heap, or the average of both roots when sizes are equal.

use std::collections::BinaryHeap;
use std::cmp::Reverse;
 
struct MedianFinder {
    lower: BinaryHeap<i32>,           // max-heap: lower half
    upper: BinaryHeap<Reverse<i32>>,  // min-heap: upper half
}
 
impl MedianFinder {
    fn new() -> Self {
        MedianFinder { lower: BinaryHeap::new(), upper: BinaryHeap::new() }
    }
 
    fn add(&mut self, val: i32) {
        // Always push to lower first
        self.lower.push(val);
        // Balance: move lower's max to upper
        self.upper.push(Reverse(self.lower.pop().unwrap()));
        // Keep lower >= upper in size
        if self.upper.len() > self.lower.len() {
            self.lower.push(self.upper.pop().unwrap().0);
        }
    }
 
    fn median(&self) -> f64 {
        if self.lower.len() > self.upper.len() {
            *self.lower.peek().unwrap() as f64
        } else {
            let l = *self.lower.peek().unwrap() as f64;
            let r = self.upper.peek().unwrap().0 as f64;
            (l + r) / 2.0
        }
    }
}
 
fn main() {
    let mut mf = MedianFinder::new();
    for x in [1, 2, 3, 4, 5] {
        mf.add(x);
        println!("after {}: median = {}", x, mf.median());
    }
    // 1.0, 1.5, 2.0, 2.5, 3.0
}

Top-K Frequent Elements

Given an array, find the k most frequent elements. Build a frequency map with a hash map, then use a min-heap of size k keyed by frequency. This runs in O(n log k) and uses O(n + k) space.

use std::collections::{HashMap, BinaryHeap};
use std::cmp::Reverse;
 
fn top_k_frequent(nums: &[i32], k: usize) -> Vec<i32> {
    let mut freq: HashMap<i32, usize> = HashMap::new();
    for &x in nums { *freq.entry(x).or_insert(0) += 1; }
 
    // min-heap: (frequency, value)
    let mut heap: BinaryHeap<Reverse<(usize, i32)>> = BinaryHeap::new();
    for (&val, &count) in &freq {
        heap.push(Reverse((count, val)));
        if heap.len() > k { heap.pop(); }
    }
    heap.into_iter().map(|Reverse((_, v))| v).collect()
}
 
fn main() {
    let nums = [1, 1, 1, 2, 2, 3];
    println!("{:?}", top_k_frequent(&nums, 2)); // [1, 2] (in some order)
}