Data Structures
  • Implement insert with bubble-up in O(log n): add at end, swap up until heap property holds
  • Implement extract max/min with bubble-down: move last to root, swap down with larger/smaller child
  • Understand heapify builds heap in O(n), better than n insertions

Heap Operations

Heaps support three core operations: insert, extract max/min, and peek. All efficient.

Insert (Push)

Add element while maintaining heap property.

Algorithm:

  1. Add element at end of array (next available spot)
  2. Bubble up (sift up) until heap property restored

Bubble up: Compare with parent. If violates heap property, swap. Repeat.

def insert(heap, value):
    heap.append(value)
    bubble_up(heap, len(heap) - 1)

def bubble_up(heap, index):
    while index > 0:
        parent = (index - 1) // 2
        
        if heap[index] > heap[parent]:  # Max heap
            heap[index], heap[parent] = heap[parent], heap[index]
            index = parent
        else:
            break

Example (max heap):

Start: [10, 8, 9, 5, 7]
Insert 12:

Step 1: Add at end
[10, 8, 9, 5, 7, 12]

Step 2: Bubble up
12 > 7 (parent)? Yes, swap
[10, 8, 9, 5, 12, 7]

12 > 8 (parent)? Yes, swap
[10, 12, 9, 5, 8, 7]

12 > 10 (parent)? Yes, swap
[12, 10, 9, 5, 8, 7]

Done. 12 is root.

O(log n). At most swap from leaf to root (tree height).

Extract Max/Min

Remove and return root (max in max heap, min in min heap).

Algorithm:

  1. Save root value
  2. Move last element to root
  3. Bubble down (sift down) until heap property restored

Bubble down: Compare with children. If violates heap property, swap with larger child (max heap) or smaller child (min heap). Repeat.

def extract_max(heap):
    if not heap:
        return None
    
    max_val = heap[0]
    heap[0] = heap[-1]
    heap.pop()
    
    if heap:
        bubble_down(heap, 0)
    
    return max_val

def bubble_down(heap, index):
    n = len(heap)
    
    while True:
        largest = index
        left = 2 * index + 1
        right = 2 * index + 2
        
        if left < n and heap[left] > heap[largest]:
            largest = left
        
        if right < n and heap[right] > heap[largest]:
            largest = right
        
        if largest != index:
            heap[index], heap[largest] = heap[largest], heap[index]
            index = largest
        else:
            break

Example (max heap):

Start: [10, 8, 9, 5, 7, 6]

Step 1: Save root (10), move last to root
[6, 8, 9, 5, 7]

Step 2: Bubble down
6 < 8 or 9? Yes, swap with 9 (larger child)
[9, 8, 6, 5, 7]

6 < 5 or 7? Yes, swap with 7
[9, 8, 7, 5, 6]

Done.

O(log n). At most swap from root to leaf.

Peek

Return root without removing.

def peek(heap):
    return heap[0] if heap else None

O(1). Just array access.

Complete Implementation

class MaxHeap:
    def __init__(self):
        self.heap = []
    
    def insert(self, value):
        self.heap.append(value)
        self._bubble_up(len(self.heap) - 1)
    
    def extract_max(self):
        if not self.heap:
            return None
        
        max_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        
        if self.heap:
            self._bubble_down(0)
        
        return max_val
    
    def peek(self):
        return self.heap[0] if self.heap else None
    
    def _bubble_up(self, index):
        while index > 0:
            parent = (index - 1) // 2
            if self.heap[index] > self.heap[parent]:
                self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
                index = parent
            else:
                break
    
    def _bubble_down(self, index):
        n = len(self.heap)
        while True:
            largest = index
            left = 2 * index + 1
            right = 2 * index + 2
            
            if left < n and self.heap[left] > self.heap[largest]:
                largest = left
            
            if right < n and self.heap[right] > self.heap[largest]:
                largest = right
            
            if largest != index:
                self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
                index = largest
            else:
                break

# Usage
heap = MaxHeap()
heap.insert(10)
heap.insert(5)
heap.insert(15)
heap.insert(3)

print(heap.peek())  # 15
print(heap.extract_max())  # 15
print(heap.peek())  # 10

Decrease Key / Increase Key

Change a value, restore heap property.

Increase key (max heap):

def increase_key(heap, index, new_value):
    if new_value < heap[index]:
        raise ValueError("New value smaller")
    
    heap[index] = new_value
    bubble_up(heap, index)

Increase value, bubble up. O(log n).

Decrease key (max heap):

def decrease_key(heap, index, new_value):
    if new_value > heap[index]:
        raise ValueError("New value larger")
    
    heap[index] = new_value
    bubble_down(heap, index)

Decrease value, bubble down. O(log n).

Heapify (Build Heap)

Build heap from unsorted array.

Naive: Insert each element. O(n log n).

Heapify: Bottom-up. O(n).

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

def bubble_down(arr, index, n):
    while True:
        largest = index
        left = 2 * index + 1
        right = 2 * index + 2
        
        if left < n and arr[left] > arr[largest]:
            largest = left
        
        if right < n and arr[right] > arr[largest]:
            largest = right
        
        if largest != index:
            arr[index], arr[largest] = arr[largest], arr[index]
            index = largest
        else:
            break

arr = [3, 9, 2, 1, 4, 5]
heapify(arr)
print(arr)  # [9, 4, 5, 1, 3, 2] (max heap)

Why O(n)? Most nodes are near bottom (don't bubble far). Math works out to O(n).

Delete Arbitrary Element

Remove element at index i.

def delete(heap, index):
    if index >= len(heap):
        return
    
    heap[index] = heap[-1]
    heap.pop()
    
    if index < len(heap):
        parent = (index - 1) // 2 if index > 0 else -1
        
        if parent >= 0 and heap[index] > heap[parent]:
            bubble_up(heap, index)
        else:
            bubble_down(heap, index)

Replace with last element. Bubble up or down depending on comparison. O(log n).

Heap Sort

Sort using heap.

def heap_sort(arr):
    # Build max heap
    heapify(arr)
    
    # Extract max repeatedly
    for i in range(len(arr) - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # Move max to end
        bubble_down(arr, 0, i)  # Restore heap for remaining
    
    return arr

arr = [3, 9, 2, 1, 4, 5]
print(heap_sort(arr))  # [1, 2, 3, 4, 5, 9]

O(n log n). Heapify O(n), then n extractions of O(log n) each.

In-place. No extra space.

Performance Summary

Operation Time Complexity
Insert O(log n)
Extract max/min O(log n)
Peek O(1)
Heapify O(n)
Increase/decrease key O(log n)
Delete arbitrary O(log n)
Heap sort O(n log n)

Space: O(1) auxiliary (in-place operations on array).

Common Mistakes

Forgetting to bubble after modifications:

# Wrong: just change value
heap[index] = new_value

# Right: change and restore heap property
heap[index] = new_value
bubble_up(heap, index)  # or bubble_down

Wrong bubble direction:

Increase key in max heap? Bubble up (might violate parent).
Decrease key in max heap? Bubble down (might violate children).

Off-by-one in index calculations:

Parent: (i - 1) // 2, not i // 2.
Left child: 2i + 1, not 2i.

The Pattern

Heap operations maintain heap property through bubbling:

  • Insert: add at end, bubble up
  • Extract: move last to root, bubble down
  • Modify: change value, bubble in appropriate direction

Understanding operations means understanding when to bubble up vs down.

Master these, and you'll implement heaps and solve priority queue problems efficiently.