🌳 Heap Fundamentals

🎯 What is a Heap?

A heap is a specialized tree-based data structure that satisfies the heap property. It is a complete binary tree where each node's value is either greater than or equal to (max-heap) or less than or equal to (min-heap) its children's values.

Complete Binary Tree: All levels filled except possibly the last, filled left to right
Heap Property: Parent ≥ Children (Max-Heap) or Parent ≤ Children (Min-Heap)
Implementation: Usually an array (implicit tree)
Key Operations: Insert, Extract-Min/Max, Peek, Delete

📌 Complete Binary Tree📌 Array Implementation📌 O(log n) Operations

The Core Insight

Key Insight: Heaps provide an efficient way to maintain a collection of elements where we need quick access to the minimum or maximum element. This is the foundation of priority queues.

Two Main Types:

Min-Heap Smallest element at root (parent ≤ children)
Max-Heap Largest element at root (parent ≥ children)

# Heap Representation as Array
# For a node at index i:
#   Left child: 2*i + 1
#   Right child: 2*i + 2
#   Parent: (i - 1) // 2

# Example Max-Heap: [10, 8, 7, 6, 5, 4, 3]
#   10
#  /  \
# 8    7
# / \  / \
#6  5 4  3

# Example Min-Heap: [3, 5, 4, 8, 6, 7, 10]
#   3
#  /  \
# 5    4
# / \  / \
#8  6 7  10

📉 Min-Heap

🎯 Smallest Element at Root

A 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 minimum element is always at the root.

Property: parent ≤ children for all nodes
Root: Minimum element
Use Cases: Priority queues, Dijkstra's algorithm, Huffman coding
Operations: O(log n) insert/extract, O(1) peek

# Min-Heap Implementation
class MinHeap:
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def insert(self, key):
        self.heap.append(key)
        self._heapify_up(len(self.heap) - 1)
    
    def _heapify_up(self, i):
        while i > 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)
    
    def extract_min(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        
        min_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return min_val
    
    def _heapify_down(self, i):
        smallest = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        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 != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self._heapify_down(smallest)
    
    def get_min(self):
        return self.heap[0] if self.heap else None
    
    def size(self):
        return len(self.heap)

# Example Usage
heap = MinHeap()
heap.insert(5)
heap.insert(3)
heap.insert(8)
heap.insert(1)
print(heap.extract_min())  # 1
print(heap.get_min())      # 3

📈 Max-Heap

🎯 Largest Element at Root

A 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 maximum element is always at the root.

Property: parent ≥ children for all nodes
Root: Maximum element
Use Cases: Heap sort, priority queues (max priority)
Operations: O(log n) insert/extract, O(1) peek

# Max-Heap Implementation
class MaxHeap:
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def insert(self, key):
        self.heap.append(key)
        self._heapify_up(len(self.heap) - 1)
    
    def _heapify_up(self, i):
        while i > 0 and self.heap[self.parent(i)] < self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)
    
    def extract_max(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        
        max_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return max_val
    
    def _heapify_down(self, i):
        largest = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        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 != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self._heapify_down(largest)
    
    def get_max(self):
        return self.heap[0] if self.heap else None
    
    def size(self):
        return len(self.heap)

# Example Usage
heap = MaxHeap()
heap.insert(5)
heap.insert(3)
heap.insert(8)
heap.insert(1)
print(heap.extract_max())  # 8
print(heap.get_max())      # 5

⚙️ Heap Operations

🎯 Core Heap Operations

Insert (push): Add element at end, bubble up (heapify up)
Extract (pop): Remove root, replace with last, bubble down (heapify down)
Peek (top): Return root element without removing
Delete: Remove arbitrary element (requires searching)
Increase/Decrease Key: Update value and adjust heap
Merge: Combine two heaps (O(n) for binary heap)

# Advanced Heap Operations

# Decrease Key (Min-Heap)
def decrease_key(heap, i, new_val):
    if new_val > heap[i]:
        raise ValueError("New value is greater than current")
    heap[i] = new_val
    # Bubble up
    while i > 0 and heap[parent(i)] > heap[i]:
        heap[i], heap[parent(i)] = heap[parent(i)], heap[i]
        i = parent(i)

# Increase Key (Max-Heap)
def increase_key(heap, i, new_val):
    if new_val < heap[i]:
        raise ValueError("New value is smaller than current")
    heap[i] = new_val
    # Bubble up
    while i > 0 and heap[parent(i)] < heap[i]:
        heap[i], heap[parent(i)] = heap[parent(i)], heap[i]
        i = parent(i)

# Delete arbitrary element
def delete_key(heap, i):
    # For min-heap: decrease to -inf, then extract min
    # For max-heap: increase to +inf, then extract max
    if i < 0 or i >= len(heap):
        return
    # Swap with last element and remove
    heap[i] = heap[-1]
    heap.pop()
    # Heapify down from i
    heapify_down(heap, i)

🏗️ Heapify & Build Heap

🎯 Efficiently Building a Heap

Heapify is the process of converting an arbitrary array into a heap. Building a heap from an array can be done in O(n) time using the bottom-up approach.

Bottom-Up Heapify: Start from last non-leaf node and heapify down
Time Complexity: O(n) - more efficient than n inserts
Space: O(1) in-place

# Heapify - Build Heap from Array
def heapify_min(arr, n, i):
    smallest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] < arr[smallest]:
        smallest = left
    if right < n and arr[right] < arr[smallest]:
        smallest = right
    
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        heapify_min(arr, n, smallest)

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

# Example
arr = [4, 10, 3, 5, 1, 8, 2]
build_min_heap(arr)
print(arr)  # [1, 4, 2, 5, 10, 8, 3]
#          1
#        /   \
#       4     2
#      / \   / \
#     5  10 8   3

# Why O(n)? The work done at each level:
# Level 0: n/2 operations
# Level 1: n/4 operations
# Level 2: n/8 operations
# ...
# Total: n/2 + n/4 + n/8 + ... = O(n)

🔄 Heap Sort

🎯 Sorting with Heaps

Heap sort uses the heap data structure to sort an array in O(n log n) time. It builds a max-heap and repeatedly extracts the maximum element.

Approach: Build max-heap, repeatedly extract max
Time: O(n log n) worst, average, best
Space: O(1) in-place
Stability: Not stable

# Heap Sort Implementation
def heapify_max(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_max(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    
    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        heapify_max(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 root with last
        heapify_max(arr, i, 0)  # Heapify reduced heap
    
    return arr

# Example
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print(arr)  # [5, 6, 7, 11, 12, 13]

# Step-by-step:
# 1. Build max-heap: [13, 11, 12, 5, 6, 7]
# 2. Swap 13 with 7: [7, 11, 12, 5, 6, 13]
# 3. Heapify: [12, 11, 7, 5, 6, 13]
# 4. Swap 12 with 6: [6, 11, 7, 5, 12, 13]
# ... continues until sorted

🎯 Priority Queue

🎯 The Most Common Use of Heaps

A priority queue is an abstract data type that operates like a queue but where each element has a priority. Elements with higher priority are dequeued before lower priority elements.

Implementation: Usually a binary heap
Operations: Push (insert), Pop (extract min/max)
Applications: Dijkstra's algorithm, event simulation, job scheduling

# Priority Queue using Python's heapq
import heapq

# Min-Heap Priority Queue
class PriorityQueue:
    def __init__(self):
        self.heap = []
    
    def push(self, item, priority):
        # In Python, heapq is min-heap by default
        heapq.heappush(self.heap, (priority, item))
    
    def pop(self):
        if self.is_empty():
            return None
        priority, item = heapq.heappop(self.heap)
        return item
    
    def peek(self):
        if self.is_empty():
            return None
        return self.heap[0][1]
    
    def is_empty(self):
        return len(self.heap) == 0
    
    def size(self):
        return len(self.heap)

# Example Usage
pq = PriorityQueue()
pq.push("task1", 2)
pq.push("task2", 1)
pq.push("task3", 3)

print(pq.pop())  # task2 (priority 1)
print(pq.pop())  # task1 (priority 2)
print(pq.pop())  # task3 (priority 3)

# Custom comparator for max-heap priority queue
class MaxPriorityQueue:
    def __init__(self):
        self.heap = []
    
    def push(self, item, priority):
        heapq.heappush(self.heap, (-priority, item))
    
    def pop(self):
        if self.is_empty():
            return None
        priority, item = heapq.heappop(self.heap)
        return item
    
    def is_empty(self):
        return len(self.heap) == 0

📊 Binary Heap

🎯 The Standard Heap

A binary heap is a complete binary tree implemented as an array. It's the most common heap implementation due to its simplicity and efficiency.

Complete Tree: All levels filled, last level filled left to right
Array Implementation: No pointers needed, cache-friendly
Time: O(log n) insert/extract, O(1) peek
Limitations: Slow merge (O(n)), no decrease-key efficiently

# Binary Heap - Full Implementation with Generic Comparator
class BinaryHeap:
    def __init__(self, is_min_heap=True):
        self.heap = []
        self.is_min_heap = is_min_heap
    
    def _compare(self, a, b):
        # Returns True if a should be above b
        if self.is_min_heap:
            return a < b
        return a > b
    
    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def insert(self, key):
        self.heap.append(key)
        self._bubble_up(len(self.heap) - 1)
    
    def _bubble_up(self, i):
        parent = (i - 1) // 2
        while i > 0 and self._compare(self.heap[i], self.heap[parent]):
            self._swap(i, parent)
            i = parent
            parent = (i - 1) // 2
    
    def extract(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._bubble_down(0)
        return root
    
    def _bubble_down(self, i):
        n = len(self.heap)
        while True:
            best = i
            left = 2 * i + 1
            right = 2 * i + 2
            
            if left < n and self._compare(self.heap[left], self.heap[best]):
                best = left
            if right < n and self._compare(self.heap[right], self.heap[best]):
                best = right
            
            if best == i:
                break
            
            self._swap(i, best)
            i = best
    
    def peek(self):
        return self.heap[0] if self.heap else None
    
    def size(self):
        return len(self.heap)

# Example
min_heap = BinaryHeap(True)
max_heap = BinaryHeap(False)

for val in [5, 3, 8, 1, 7]:
    min_heap.insert(val)
    max_heap.insert(val)

print(min_heap.extract())  # 1
print(max_heap.extract())  # 8

🌀 Fibonacci Heap

🎯 Advanced Heap for Decrease-Key

The Fibonacci heap is a more advanced heap data structure with better amortized time for decrease-key and merge operations, crucial for algorithms like Dijkstra's.

Structure: Collection of trees, lazy merging
Amortized Time: O(1) insert, merge, decrease-key
Decrease-Key: O(1) amortized (critical for Dijkstra)
Complexity: More complex implementation, higher constants

# Fibonacci Heap - Conceptual Overview
# (Simplified representation)

class FibonacciHeapNode:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.parent = None
        self.child = None
        self.left = self
        self.right = self
        self.degree = 0
        self.marked = False

class FibonacciHeap:
    def __init__(self):
        self.min_node = None
        self.size = 0
    
    def insert(self, key, value=None):
        node = FibonacciHeapNode(key, value)
        if self.min_node is None:
            self.min_node = node
        else:
            # Add to root list
            self.min_node.left.right = node
            node.left = self.min_node.left
            node.right = self.min_node
            self.min_node.left = node
            if key < self.min_node.key:
                self.min_node = node
        self.size += 1
        return node
    
    def extract_min(self):
        if self.min_node is None:
            return None
        
        min_node = self.min_node
        
        # Add children to root list
        if min_node.child is not None:
            child = min_node.child
            while True:
                next_child = child.right
                child.parent = None
                if next_child == min_node.child:
                    break
                child = next_child
            
            # Merge child list with root list
            min_node.left.right = min_node.child
            min_node.child.left = min_node.left
            min_node.left = min_node.child
            min_node.child.right = min_node
        
        # Remove min_node from root list
        if min_node.right == min_node:
            self.min_node = None
        else:
            min_node.left.right = min_node.right
            min_node.right.left = min_node.left
            self.min_node = min_node.right
            self._consolidate()
        
        self.size -= 1
        return min_node
    
    def _consolidate(self):
        # Merge trees of same degree
        # Complex implementation omitted
        pass
    
    def decrease_key(self, node, new_key):
        # O(1) amortized
        node.key = new_key
        parent = node.parent
        if parent is not None and node.key < parent.key:
            self._cut(node, parent)
            self._cascade_cut(parent)
        if node.key < self.min_node.key:
            self.min_node = node
    
    def _cut(self, node, parent):
        # Cut node from parent
        pass
    
    def _cascade_cut(self, node):
        # Propagate cuts up the tree
        pass

# Key Advantage: Decrease-key is O(1) amortized
# Used in Dijkstra's algorithm: O(E + V log V)

🌲 Binomial Heap

🎯 Efficient Merge

A binomial heap is a collection of binomial trees that supports efficient merge operations, making it useful for applications that require frequent heap merging.

Structure: Collection of binomial trees
Merge: O(log n) - better than binary heap
Operations: O(log n) for insert, extract, delete
Use Case: When merge operations are frequent

# Binomial Heap - Conceptual Overview
class BinomialNode:
    def __init__(self, key):
        self.key = key
        self.degree = 0
        self.parent = None
        self.child = None
        self.sibling = None

class BinomialHeap:
    def __init__(self):
        self.head = None  # Head of the root list
        self.size = 0
    
    def merge(self, h1, h2):
        # Merge two binomial heaps (O(log n))
        # Combine root lists by degree
        pass
    
    def insert(self, key):
        # Create a new heap with single node
        # Merge with current heap
        pass
    
    def extract_min(self):
        # Find minimum in root list
        # Remove it and merge its children
        pass
    
    def union(self, other):
        # Unite two heaps
        pass
    
    def decrease_key(self, node, new_key):
        # Update key and bubble up
        pass

# Binomial Tree Properties:
# - B0: single node
# - Bk: two Bk-1 trees linked together
# - Number of nodes in Bk: 2^k
# - Height of Bk: k
# - Degree of root: k

# Binary representation of heap size
# Example: size = 13 (1101) → B3, B2, B0

⚖️ Heap Comparison

Operation	Binary Heap	Binomial Heap	Fibonacci Heap
Insert	O(log n)	O(log n)	O(1)*
Extract Min	O(log n)	O(log n)	O(log n)*
Merge	O(n)	O(log n)	O(1)*
Decrease Key	O(log n)	O(log n)	O(1)*
Delete	O(log n)	O(log n)	O(log n)*
Peek	O(1)	O(1)	O(1)
Implementation	Simple	Moderate	Complex
Cache Locality	Excellent	Poor	Poor

* Amortized time (Fibonacci Heap)

⏱️ Time & Space Complexities

Operation	Time (Binary Heap)	Space	Notes
Insert	O(log n)	O(1)	Bubble up
Extract Min/Max	O(log n)	O(1)	Bubble down
Peek	O(1)	O(1)	Root element
Delete	O(log n)	O(1)	Swap with last, bubble down
Decrease Key	O(log n)	O(1)	Bubble up
Increase Key	O(log n)	O(1)	Bubble up or down
Build Heap	O(n)	O(1)	Heapify
Merge	O(n)	O(n)	For binary heap
Heap Sort	O(n log n)	O(1)	In-place

🌍 Real-World Applications

Priority Queues: Task scheduling, event simulation
Dijkstra's Algorithm: Shortest path using min-heap
Huffman Coding: Building optimal prefix codes
Heap Sort: In-place sorting algorithm
Median Maintenance: Two heaps for streaming data
K-way Merge: Merging k sorted lists
Operating Systems: Process scheduling (priority queues)
Network Routing: Routing algorithms
AI Search: A* algorithm (priority queue)

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic: "Implement a Min-Heap/Max-Heap"
Heap Sort: "Sort an array using heap sort"
K-th Largest: "Find the k-th largest element in an array"
K-way Merge: "Merge k sorted linked lists"
Median: "Find the median of a streaming data stream"
Top K: "Find the top k frequent elements"
Dijkstra: "Shortest path using a min-heap"
Meeting Rooms: "Meeting room scheduling with priority queue"

# Interview Problem: Find K-th Largest Element
def find_kth_largest(nums, k):
    import heapq
    # Use min-heap of size k
    heap = []
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        elif num > heap[0]:
            heapq.heapreplace(heap, num)
    return heap[0]

# Interview Problem: Median of a Stream
class MedianFinder:
    def __init__(self):
        self.min_heap = []  # Right half (min-heap)
        self.max_heap = []  # Left half (max-heap, stored as negative)
    
    def add_num(self, num):
        import heapq
        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.0

# Interview Problem: Merge K Sorted Lists
def merge_k_lists(lists):
    import heapq
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    
    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        if elem_idx + 1 < len(lists[list_idx]):
            heapq.heappush(heap, (lists[list_idx][elem_idx + 1], list_idx, elem_idx + 1))
    
    return result