Min-Heap Priority Queue using Array Math
Priority task schedulers require $O(\log N)$ insertions and minimum extractions. A binary min-heap maps an entire balanced binary tree into a flat array using integer math: parent at `(i - 1) // 2`, left child at `2*i + 1`, and right child at `2*i + 2`, achieving cache-locality without node pointers ⛰️🔢⚡.
class MiniHeap:
def __init__(self): self.arr = []
def push(self, val):
self.arr.append(val)
idx = len(self.arr) - 1
while idx > 0 and self.arr[idx] < self.arr[(p := (idx - 1) // 2)]:
self.arr[idx], self.arr[p] = self.arr[p], self.arr[idx]
idx = p
h = MiniHeap()
for x in [40, 10, 30]: h.push(x)
print("Root Minimum:", h.arr[0])
# 19. Min-Heap Priority Queue using Array Math Amateur programmers create linked-list trees with `left` and `right` object pointers to implement binary search trees and heaps. Every pointer adds 8 bytes of overhead and scatters nodes across random memory addresses, destroying CPU cache efficiency 🛑. ```python # The Array-Backed Complete Binary Tree: # 10 (idx 0) # / \ # (idx 1) 20 30 (idx 2) # / \ # (idx 3) 50 80 (idx 4) # # Sequential Flat Array: [10, 20, 30, 50, 80] # Left Child of idx: 2*idx + 1 # Right Child of idx: 2*idx + 2 # Parent of idx: (idx - 1) // 2 ``` ### The Sift Mechanics - **`push(val)`**: Append to the end of the flat array. While `val < parent`, swap with parent (`_sift_up`). Maximum swaps: $\log_2 N$. - **`pop()`**: Save root element `heap[0]`. Move the last element to the root position and pop the tail. Sift downward by swapping with the smaller of its two children (`_sift_down`) until the min-heap property is restored ⛰️🔢⚡! --- ### Interactive Pop-Quiz 🧠 #### In a 0-indexed binary heap array, at which index is the left child of node i located? - [ ] 2 * i + 1 ⛰️ - [ ] i // 2 - [ ] 2 * i + 2 - [ ] i + 1 --- ### Practical Challenge 🎯 Implement `MinHeap` from scratch without importing `heapq`. Implement `push(val)` with upward sifting, and `pop() -> val` swapping the root with the last element and sifting downward. Insert `[50, 20, 80, 10, 30]`. Extract all 5 elements in sequence, assert they pop in ascending order `[10, 20, 30, 50, 80]`, and print results. <details> <summary>Solution</summary> ```python class MinHeap: def __init__(self): self.heap = [] def push(self, val): self.heap.append(val) self._sift_up(len(self.heap) - 1) def pop(self): if not self.heap: raise IndexError("Empty heap") if len(self.heap) == 1: return self.heap.pop() min_val = self.heap[0] self.heap[0] = self.heap.pop() self._sift_down(0) return min_val def _sift_up(self, idx): parent = (idx - 1) // 2 while idx > 0 and self.heap[idx] < self.heap[parent]: self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx] idx = parent parent = (idx - 1) // 2 def _sift_down(self, idx): n = len(self.heap) while True: left = 2 * idx + 1 right = 2 * idx + 2 smallest = idx if left < n and self.heap[left] < self.heap[smallest]: smallest = left if right < n and self.heap[right] < self.heap[smallest]: smallest = right if smallest != idx: self.heap[idx], self.heap[smallest] = self.heap[smallest], self.heap[idx] idx = smallest else: break h = MinHeap() for v in [50, 20, 80, 10, 30]: h.push(v) popped = [h.pop() for _ in range(5)] assert popped == [10, 20, 30, 50, 80] print(f"MinHeap verified: popped in order -> {popped}") ``` </details>