DSA — Heaps

What is a Heap?

A complete binary tree where parent is greater (max-heap) or smaller (min-heap) than children.

class MinHeap:
    def __init__(self):
        self.heap = []
    
    def insert(self, data):
        self.heap.append(data)
        self._bubble_up(len(self.heap) - 1)
    
    def extract_min(self):
        if len(self.heap) > 0:
            min_val = self.heap[0]
            self.heap[0] = self.heap[-1]
            self.heap.pop()
            self._bubble_down(0)
            return min_val
    
    def _bubble_up(self, index):
        parent = (index - 1) // 2
        while index > 0 and self.heap[index] < self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            index = parent
            parent = (index - 1) // 2
    
    def _bubble_down(self, index):
        smallest = index
        left = 2 * index + 1
        right = 2 * index + 2
        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 != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._bubble_down(smallest)

Operations

Operation	Time Complexity
Insert	O(log n)
Extract	O(log n)
Peek	O(1)

Mini Practice

1. Implement a min-heap
2. Implement a max-heap
3. Use heap for sorting
4. Find kth largest element

Up Next

Continue with Priority Queues — priority queue data structure.