This lesson on Binary Search Trees & Heaps is hands-on and example-driven. You will implement an array-based Max Heap in Python without pointer overhead by leveraging complete binary tree index formulas. You will master O(log N) element insertion and extraction, and convert raw arrays into valid heaps in optimal O(N) time.

What You'll Be Able To Do

• Calculate parent, left child, and right child array indices using zero-indexed arithmetic.
• Implement the heapify_up method to restore max-heap invariants after an insertion.
• Implement extract_max and heapify_down to remove the root element in O(log N) time.
• Construct a valid max heap from an unsorted array in O(N) time using bottom-up heapification.

Detailed Concept Walkthrough

1. Array Representation of Complete Binary Trees

A complete binary tree has every level fully filled except possibly the last, which fills left to right. This structural constraint allows tree nodes to be mapped directly into a contiguous array without pointers.

• Index Arithmetic: For any node at index i, its left child resides at 2*i + 1, its right child at 2*i + 2, and its parent at (i - 1) // 2.
• Under the Hood: Contiguous storage eliminates pointer memory overhead and provides optimal CPU cache locality during tree traversals.
• Boundary Checking: Index lookup operations must check bounds against len(array) to ensure a node's computed child indices represent valid, existing nodes.

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

Key Takeaway: Contiguous arrays represent complete binary trees with zero pointer overhead using simple index arithmetic.

2. Insertion and Heapify Up

Inserting an element appends it to the end of the array to preserve structural completeness, followed by bubbling it up to restore the max-heap ordering property.

• Mechanism: The new element is appended to the list and iteratively compared with its parent node.
• Execution Flow: If the inserted value is greater than its parent, the two values are swapped, and the index moves up to the parent.
• Best Practice: The loop terminates as soon as the node reaches the root (i == 0) or is no longer greater than its parent, guaranteeing $\mathcal{O}(\log N)$ worst-case time.

def insert(self, val):
    self.heap.append(val)
    self._heapify_up(len(self.heap) - 1)

def _heapify_up(self, i):
    while i > 0 and self.heap[i] > self.heap[self.parent(i)]:
        p = self.parent(i)
        self.heap[i], self.heap[p] = self.heap[p], self.heap[i]
        i = p

Key Takeaway: Insert at the end and bubble up along ancestor nodes to restore heap properties in logarithmic time.

3. Extraction and Heapify Down

Extracting the maximum element removes the root value, replaces it with the last element in the array, and sifts that element downward to its correct position.

• Mechanism: The root element (heap[0]) is swapped with the last element (heap[-1]), popped in $\mathcal{O}(1)$ time, and the replacement root is sifted down.
• Comparison Logic: The current node is compared against both its left and right children to find the largest of the three.
• Execution Flow: If a child is larger than the current node, the node swaps with the largest child and continues sifting down recursively or iteratively.

def extract_max(self):
    if not self.heap:
        return None
    if len(self.heap) == 1:
        return self.heap.pop()
    root_val = self.heap[0]
    self.heap[0] = self.heap.pop()
    self._heapify_down(0)
    return root_val

def _heapify_down(self, i):
    largest = i
    left, right = self.left_child(i), self.right_child(i)
    n = len(self.heap)
    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 != i:
        self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
        self._heapify_down(largest)

Key Takeaway: Swap the root with the last leaf, pop the max, and sift down to restore max-heap order in O(log N) time.

4. Linear Time Heap Construction

An arbitrary array is converted into a valid heap in linear time by running heapify-down in reverse order starting from the last non-leaf node up to the root.

• Starting Point: All elements from index $N // 2$ to $N - 1$ are leaf nodes and already satisfy the heap property vacuously, so processing starts at index $N // 2 - 1$.
• Under the Hood: Most nodes are near the leaves and have very short downward paths (height $h$), bounding the total swaps to $\sum \frac{N}{2^{h+1}} \mathcal{O}(h) = \mathcal{O}(N)$.
• Best Practice: Build the heap in place from an existing array rather than performing $N$ successive inserts to avoid $\mathcal{O}(N \log N)$ overhead.

def build_heap(self, arr):
    self.heap = arr[:]
    n = len(self.heap)
    # Start from last non-leaf node and sift down to the root
    for i in range(n // 2 - 1, -1, -1):
        self._heapify_down(i)

Key Takeaway: Building a heap bottom-up runs in O(N) because the majority of nodes reside near leaf levels with minimal height.

Topics Covered in Binary Search Trees & Heaps

1. Heap Structural Properties (0:00 - 0:34) — Covers complete binary tree requirements and contrasts max heap vs min heap ordering constraints.
2. Array Index Calculations (0:34 - 1:27) — Derives zero-indexed parent and child arithmetic formulas for contiguous tree representation.
3. MaxHeap Class Initialization (1:27 - 1:42) — Sets up the internal list structure and helper methods for array navigation.
4. Insertion and Heapify Up (1:42 - 2:53) — Appends new values to the array end and bubbles them upward to preserve heap ordering.
5. Extraction Overview (2:53 - 4:21) — Explains root extraction by swapping with the tail element and initiating top-down restoration.
6. Heapify Down Logic (4:21 - 5:08) — Walks through child comparisons and swapping with the larger child down to leaf nodes.
7. Bottom-Up Heap Construction (5:08 - 5:58) — Identifies the last non-leaf index and outlines iterating backward to the root.
8. O(N) Complexity Derivation (6:21 - 7:23) — Calculates the summation of node heights across tree levels to prove linear time construction.
9. Build Heap Implementation (7:23 - 7:41) — Implements the complete build_heap routine using iterative calls to heapify_down.

DSA for Interviews Cheat Sheet

• parent(i) — Computes parent index from child index

  p = (i - 1) // 2
  

• left_child(i) — Computes left child index

  left = 2 * i + 1
  

• right_child(i) — Computes right child index

  right = 2 * i + 2
  

• last_non_leaf(n) — Finds starting index for heap construction

  start_idx = (len(arr) // 2) - 1
  

• insert(val) — Appends value and restores heap upward

  heap.append(val); _heapify_up(len(heap) - 1)
  

• extract_max() — Removes root and sifts replacement downward

  heap[0] = heap.pop(); _heapify_down(0)
  

Comparison Table

Common Pitfalls

• Mistake: Swapping with an arbitrary child during heapify down instead of the largest. Avoid: Always compare both children and swap exclusively with the larger child.
• Mistake: Starting the build heap iteration from the last element N - 1. Avoid: Start from index N // 2 - 1 because leaf nodes are already valid heaps.
• Mistake: Forgetting boundary checks when calculating child indices in array lookups. Avoid: Verify that child indices are strictly less than array length before indexing.
• Mistake: Removing the root directly from the front of the array list. Avoid: Overwrite the root with the popped tail element to prevent O(N) array shifts.

FAQs

• Why is build_heap O(N) instead of O(N log N)? Most nodes reside near the bottom with minimal heights, so the sum of all downward paths converges to O(N).
• Can an array containing null gaps represent a binary heap? No, heaps must be complete binary trees so that array indices remain contiguous without null gaps.
• How does 1-based indexing change the arithmetic formulas? For index i, the parent is i // 2, left child is 2 * i, and right child is 2 * i + 1.

Binary Search Trees: Course Supplement

The existing video covers binary heaps. This companion covers the binary search tree invariant and operations; a heap and a BST answer different query needs.

Invariant and operations

For a strict-unique-key BST, every key in a node's left subtree is smaller and every key in its right subtree is larger. Searching follows one root-to-leaf path, taking O(h) time where h is tree height. In-order traversal emits keys in ascending order. A balanced tree has h = O(log N); an unbalanced tree can have h = O(N).

def search(root, target):
    node = root
    while node is not None and node.value != target:
        node = node.left if target < node.value else node.right
    return node

Insertion follows the same comparisons until it finds an empty child position. First specify a duplicate policy: reject duplicates, count multiplicity, or consistently place equal keys on one side. Do not mix policies between search, insertion, and deletion.

Deletion cases

1. Leaf: remove the parent link.
2. One child: replace the node with its child.
3. Two children: replace the value with the in-order successor (minimum of the right subtree) or predecessor, then delete that replacement node from its old position.

When implementing recursively, return the possibly changed subtree root from every call; otherwise root deletion can be lost. For interview solutions, state that an ordinary BST is not self-balancing. A heap gives fast access to one extremum, while a BST supports ordered search, predecessor/successor, and range traversal.