🏔️ Heaps & Priority Queues Made Easy

# Let's build a max heap step by step! class MaxHeap: def __init__(self): # We use a list to store our heap - it's that simple! self.heap = [] def parent(self, i): # Parent is always at (i-1)/2 - like going up a family tree! return (i - 1) // 2 def left_child(self, i): # Left child is at 2*i + 1 return 2 * i + 1 def right_child(self, i): # Right child is at 2*i + 2 return 2 * i + 2 def insert(self, value): # Step 1: Add to the end (like joining a queue) self.heap.append(value) # Step 2: Bubble up until we find the right spot! self._bubble_up(len(self.heap) - 1) def _bubble_up(self, i): # Keep swapping with parent if we're bigger while i > 0 and self.heap[i] > self.heap[self.parent(i)]: # Swap with parent parent_idx = self.parent(i) self.heap[i], self.heap[parent_idx] = self.heap[parent_idx], self.heap[i] i = parent_idx # Move up and continue def extract_max(self): if not self.heap: return None # Save the champion (root) max_val = self.heap[0] # Move last element to root self.heap[0] = self.heap[-1] self.heap.pop() # Let it sink down to its proper place if self.heap: self._bubble_down(0) return max_val def _bubble_down(self, i): # Keep swapping with larger child until we're in the right spot while self.left_child(i) < len(self.heap): # Find the bigger child bigger_child = self.left_child(i) right = self.right_child(i) if right < len(self.heap) and self.heap[right] > self.heap[bigger_child]: bigger_child = right # If we're bigger than both children, we're done! if self.heap[i] >= self.heap[bigger_child]: break # Otherwise, swap and continue self.heap[i], self.heap[bigger_child] = self.heap[bigger_child], self.heap[i] i = bigger_child # Let's test our heap! heap = MaxHeap() numbers = [10, 20, 15, 30, 40] for num in numbers: heap.insert(num) print(f"Inserted {num}, heap: {heap.heap}") # Extract all elements (they come out sorted!) while heap.heap: print(f"Extracted: {heap.extract_max()}")

import heapq def find_k_largest(nums, k): """ Find K largest elements using a MIN heap of size K Counterintuitive but brilliant: Keep only K elements, smallest on top, so we can easily kick it out! """ # Use a min heap of size k min_heap = [] for num in nums: heapq.heappush(min_heap, num) # If we have more than k elements, remove the smallest if len(min_heap) > k: heapq.heappop(min_heap) # Kicks out the smallest! # What's left? The K largest elements! return min_heap # Example: Find top 3 scores scores = [50, 80, 90, 75, 95, 85, 70] top_3 = find_k_largest(scores, 3) print(f"Top 3 scores: {sorted(top_3, reverse=True)}") # [95, 90, 85]

import heapq def merge_k_sorted_lists(lists): """ Merge K sorted lists using a heap Time: O(N log K) where N = total elements, K = number of lists """ min_heap = [] result = [] # Add first element from each list to heap for i, lst in enumerate(lists): if lst: # If list is not empty # Push (value, list_index, element_index) heapq.heappush(min_heap, (lst[0], i, 0)) while min_heap: # Get smallest element val, list_idx, elem_idx = heapq.heappop(min_heap) result.append(val) # Add next element from same list if exists if elem_idx + 1 < len(lists[list_idx]): next_val = lists[list_idx][elem_idx + 1] heapq.heappush(min_heap, (next_val, list_idx, elem_idx + 1)) return result # Example: Merge sorted lists lists = [ [1, 4, 7], [2, 5, 8], [3, 6, 9] ] merged = merge_k_sorted_lists(lists) print(f"Merged: {merged}") # [1, 2, 3, 4, 5, 6, 7, 8, 9]

def heap_sort(arr): """ Heap Sort: Build max heap, then extract elements Time: O(n log n), Space: O(1) - In-place! """ n = len(arr) # Build max heap (heapify) 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): # Move root to end arr[0], arr[i] = arr[i], arr[0] # Heapify reduced heap heapify(arr, i, 0) return arr def heapify(arr, n, i): """Make subtree rooted at i a max heap""" largest = i left = 2 * i + 1 right = 2 * i + 2 # Find largest among root and children if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right # If largest is not root, swap and continue if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) # Test it! numbers = [64, 34, 25, 12, 22, 11, 90] sorted_nums = heap_sort(numbers.copy()) print(f"Sorted: {sorted_nums}")

import heapq from collections import defaultdict def dijkstra(graph, start): """ Find shortest paths from start to all vertices Using min heap for efficient vertex selection """ distances = defaultdict(lambda: float('inf')) distances[start] = 0 # Min heap: (distance, vertex) min_heap = [(0, start)] visited = set() while min_heap: curr_dist, u = heapq.heappop(min_heap) # Skip if already visited if u in visited: continue visited.add(u) # Check all neighbors for v, weight in graph[u]: if v not in visited: new_dist = curr_dist + weight # If found shorter path, update if new_dist < distances[v]: distances[v] = new_dist heapq.heappush(min_heap, (new_dist, v)) return dict(distances) # Example: City distances graph = defaultdict(list) graph['A'].extend([('B', 4), ('C', 2)]) graph['B'].extend([('C', 1), ('D', 5)]) graph['C'].extend([('D', 8), ('E', 10)]) graph['D'].append(('E', 2)) distances = dijkstra(graph, 'A') print(f"Shortest distances from A: {distances}")