Data Structures & Algorithms

Data Structure Module — Maintaining order dynamically

What You'll Learn#

1. What is a Heap?#

A heap is NOT just any binary tree. It must satisfy two strict rules:

Rule 1: Shape Property (Complete Binary Tree)#

A heap must be a Complete Binary Tree. This means the tree is filled level by level, from left to right. The last level may be incomplete, but it must be filled starting from the leftmost position.

Rule 2: Heap Property (Order)#

• Max-Heap: Parent ≥ Children (Largest element at the root)
• Min-Heap: Parent ≤ Children (Smallest element at the root)

  Max Heap:                    Min Heap:
       [90]                         [10]
      /    \                       /    \
   [70]    [50]                 [30]    [20]
   /  \    /                    /  \    /
 [30] [10][40]                [70] [50][40]

  Parent ≥ Children            Parent ≤ Children

Crucial insight: A heap is partially ordered, not fully sorted! Siblings have NO guaranteed relationship. You only know the parent is ≥ or ≤ the children.

2. The Power of Height#

Why are heap operations so fast? It's all about the height of the tree.

  Height of a heap = ⌊log₂ n⌋

Because a heap is a complete binary tree, it is always perfectly balanced.

• 1,000 nodes → Height ≈ 10
• 1,000,000 nodes → Height ≈ 20

Any operation that travels from the root to a leaf takes O(log n) time. The structure naturally bounds the worst-case performance!

3. Heapify#

Heapify is the process of restoring the heap property when a single node violates it.

Imagine a max-heap where the root is suddenly replaced by a very small number. To fix the heap, that small number must "float down" (swap with its largest child) until it reaches a valid position.

  Heapify Down (Max-Heap example):
  The root [10] violates the property.

       [10]  ← violation!
      /    \
   [70]    [50]
   /  \
 [30] [20]

  Step 1: Swap 10 with the larger child (70)
       [70]
      /    \
   [10]    [50]
   /  \
 [30] [20]

  Step 2: 10 still violates property. Swap with larger child (30)
       [70]
      /    \
   [30]    [50]
   /  \
 [10] [20]   ← Heap restored!

Complexity of Heapify:#

• Worst case: Element floats down the entire height of the tree.
• Height: ≈ log n
• Time Complexity: O(log n)

Because heapify is O(log n):

• Insert in heap (append to end, bubble up) = O(log n)
• Delete in heap (swap root with last, remove last, heapify root down) = O(log n)

4. Building a Heap from an Array#

How do we take an unsorted array and turn it into a valid heap? We call heapify() on all non-leaf nodes, starting from the last non-leaf node up to the root.

The Exam Trap: Complexity of Build Heap#

If heapify takes O(log n), and we call it n/2 times, the complexity must be O(n log n), right? WRONG.

  Build Heap from Array = O(n)

Why? Most of the nodes in a complete binary tree are at the bottom (leaves).

• Leaves don't need to be heapified (they have no children).
• Nodes one level above leaves only travel 1 step.
• Only the single root node travels the full log n steps.

When you sum the mathematical series: sum(h × nodes at height h), it tightly converges to O(n).

Exam Gold: Never say building a heap is O(n log n). It is strictly O(n).

5. Heap Sort#

Heap Sort leverages the max-heap to sort an array in place.

The Algorithm:#

1. Build Max Heap from the unsorted array (O(n)).
2. The largest element is now at the root.
3. Swap the root with the last element in the heap.
4. Reduce the heap size by 1 (the last element is now sorted at the end of the array!).
5. Heapify the new root down to restore the max-heap property (O(log n)).
6. Repeat steps 3-5 until the heap is empty.

  Step-by-step logic:
  Array: [30, 10, 50, 20, 40]

  1. Build Max Heap: [50, 40, 30, 20, 10]
  2. Swap 50 (root) with 10 (last): [10, 40, 30, 20 | 50(sorted)]
  3. Heapify root (10): [40, 20, 30, 10 | 50(sorted)]
  4. Swap 40 with 10: [10, 20, 30 | 40, 50(sorted)]
  5. Heapify root (10): [30, 20, 10 | 40, 50(sorted)]
  ... and so on.

Complexity Profile:#

Heap sort is disciplined and reliable. It never degrades to O(n²) like Quick Sort can. However, it is often slower than Quick Sort in practice due to poor cache locality (jumping around array indices).

6. Array Implementation of Heaps#

Heaps are beautifully mapped to arrays without needing node objects or pointers.

For any element at index i (using 0-based indexing):

• Left Child: 2i + 1
• Right Child: 2i + 2
• Parent: ⌊(i - 1) / 2⌋

# Python uses heapq (Min-Heap by default)
import heapq

# Start with unsorted list
arr = [30, 10, 50, 20, 40]

# Convert to heap IN-PLACE - O(n)
heapq.heapify(arr)
print(arr)  # [10, 20, 50, 30, 40] -> Root is 10

# Push - O(log n)
heapq.heappush(arr, 5)

# Pop min - O(log n)
smallest = heapq.heappop(arr)

Key Takeaways#

TL;DR - Quick Recall#

One-liner for each concept:

The Golden Rules:

1. A Heap is NOT a full sorted structure; it only guarantees the root is the extreme value.
2. Python only implements Min-Heaps. To use a Max-Heap naturally, multiply all numbers by -1 before pushing, and multiply by -1 when popping.
3. If an exam asks for sorting with O(1) space and guaranteed O(n log n) time, the answer is always Heap Sort.

Additional Resources#

Video Courses:

• Abdul Bari - Heap Sort - Detailed algorithm breakdown
• NeetCode - Priority Queue / Heap - Great visual explanations

Practice Problems:

• LeetCode 215: Kth Largest Element in an Array (Classic Heap Problem)
• LeetCode 1046: Last Stone Weight
• LeetCode 347: Top K Frequent Elements