Heap

A Heap is a specific tree-based data structure used to implement a Priority Queue. Unlike a Queue (FIFO), a Heap allows you to retrieve the element with the Highest Priority (Smallest or Largest value) in $O(\log N)$ time.

The Two Rules

1. Shape Property: It is a Complete Binary Tree. Every level is filled completely, except possibly the last level, which is filled from left to right.
2. Heap Property:
   • Min-Heap: Parent $\le$ Children. (Root is the Minimum).
   • Max-Heap: Parent $\ge$ Children. (Root is the Maximum).

Array Representation

We do not use pointers or Node classes. We store the tree in a simple flat array.

Index Math: If a node is at index i:

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

Library Implementation

Use these in Interviews/Production.

Python’s built-in module implements a Min-Heap.

• Push: heapq.heappush(list, val)
• Pop: heapq.heappop(list) (Returns smallest)
• Peek: list[0]

Rust’s standard library implements a Max-Heap.

• Push: heap.push(val)
• Pop: heap.pop() (Returns largest)
• Peek: heap.peek()

import heapq
 
# 1. Min-Heap (Default)
min_heap = []
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 5)
 
print(min_heap[0])  # Peek: 1 (Smallest)
print(heapq.heappop(min_heap))  # Pop: 1
 
# 2. Max-Heap Hack
# Python has no Max-Heap. We store NEGATIVE numbers to simulate it.
max_heap = []
val = 10
heapq.heappush(max_heap, -val)  # Store -10
print(-max_heap[0])  # Peek: 10

use std::collections::BinaryHeap;
use std::cmp::Reverse;
 
// 1. Max-Heap (Default)
let mut max_heap = BinaryHeap::new();
max_heap.push(1);
max_heap.push(10);
max_heap.push(5);
 
println!("{:?}", max_heap.peek()); // Some(10)
 
// 2. Min-Heap Hack
// We wrap values in 'Reverse' to flip the comparison logic.
let mut min_heap = BinaryHeap::new();
min_heap.push(Reverse(1));
min_heap.push(Reverse(10));
min_heap.push(Reverse(5));
 
// When popping, we unwrap the Reverse wrapper
if let Some(Reverse(val)) = min_heap.pop() {
    println!("Smallest: {}", val); // 1
}

Under the Hood

To understand HOW it works, we must implement the “Bubble Up” and “Bubble Down” logic.

The Operations

1. Push ($O(\log N)$):
   • Add value to the end of the array.
   • Bubble Up (Sift Up): Swap with parent if the order is wrong. Repeat until root or correct.
2. Pop ($O(\log N)$):
   • Swap the Root with the Last Element.
   • Remove the last element (the old root).
   • Bubble Down (Sift Down): Compare new root with children. Swap with the smaller/larger child. Repeat.

Implementation (Min-Heap)

class MinHeap:
    def __init__(self):
        self.heap = []
 
    def push(self, val: int):
        self.heap.append(val)
        self._bubble_up(len(self.heap) - 1)
 
    def pop(self) -> int:
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
 
        # 1. Swap root with last
        root_val = self.heap[0]
        self.heap[0] = self.heap.pop()  # Move last to root
 
        # 2. Bubble Down
        self._bubble_down(0)
        return root_val
 
    def _bubble_up(self, index: int):
        parent = (index - 1) // 2
        # While not root AND parent > current (Violation)
        while index > 0 and self.heap[parent] > self.heap[index]:
            self.heap[parent], self.heap[index] = self.heap[index], self.heap[parent]
            index = parent
            parent = (index - 1) // 2
 
    def _bubble_down(self, index: int):
        n = len(self.heap)
        while True:
            left = 2 * index + 1
            right = 2 * index + 2
            smallest = index
 
            # Check Left Child
            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            # Check Right Child
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right
 
            if smallest == index:
                break  # Correct position found
 
            # Swap and continue
            self.heap[index], self.heap[smallest] = (
                self.heap[smallest],
                self.heap[index],
            )
            index = smallest

pub struct MinHeap {
    items: Vec<i32>,
}
 
impl MinHeap {
    pub fn new() -> Self {
        Self { items: Vec::new() }
    }
 
    pub fn push(&mut self, val: i32) {
        self.items.push(val);
        self.bubble_up(self.items.len() - 1);
    }
 
    pub fn pop(&mut self) -> Option<i32> {
        if self.items.is_empty() {
            return None;
        }
        if self.items.len() == 1 {
            return self.items.pop();
        }
 
        let root = self.items[0];
        // Move last item to root
        self.items[0] = self.items.pop().unwrap();
        self.bubble_down(0);
        Some(root)
    }
 
    fn bubble_up(&mut self, mut index: usize) {
        while index > 0 {
            let parent = (index - 1) / 2;
            if self.items[parent] <= self.items[index] {
                break; // Order is correct
            }
            self.items.swap(parent, index);
            index = parent;
        }
    }
 
    fn bubble_down(&mut self, mut index: usize) {
        let len = self.items.len();
        loop {
            let left = 2 * index + 1;
            let right = 2 * index + 2;
            let mut smallest = index;
 
            if left < len && self.items[left] < self.items[smallest] {
                smallest = left;
            }
            if right < len && self.items[right] < self.items[smallest] {
                smallest = right;
            }
 
            if smallest == index {
                break;
            }
 
            self.items.swap(index, smallest);
            index = smallest;
        }
    }
}

Complexity Analysis

Operation	Complexity	Why?
Push	$O(\log N)$	We traverse the height of the tree (bubble up).
Pop	$O(\log N)$	We traverse the height of the tree (bubble down).
Peek	$O(1)$	Just look at index 0.
Build Heap	$O(N)$	If we “heapify” an array all at once (not one by one), mathematics proves it takes linear time.