Unit 5: Heaps, Hashing & Graphs

Industry Hook — The Real-World Problem First

Concept Explanation — Theory, Earned

2.1 Heaps & HeapSort

Layer 1 — Intuition

A heap is like a VIP hospital queue. The patient with the highest severity (priority) is always treated first. You can add new patients and the most critical one automatically "bubbles up" to the front. A max-heap keeps the maximum at the root; a min-heap keeps the minimum.

Layer 2 — Visual

Max-Heap (parent ≥ children)
           90
         /    \
       80      70
      /  \    /
    50   60  30

Array: [90, 80, 70, 50, 60, 30]  (level-order)

For index i:
  Parent:      (i-1)/2
  Left child:  2i + 1
  Right child: 2i + 2

Heap Property: arr[parent] ≥ arr[child] (max-heap)
               arr[parent] ≤ arr[child] (min-heap)

Heap Operations

2.2 Hashing & Hash Tables

Layer 1 — Intuition

A hash table is like a library with numbered shelves. Instead of searching every shelf, you compute a shelf number from the book title: "Harry Potter" → shelf 7. Go directly to shelf 7. Done in O(1).

Layer 2 — Hash Function & Collisions

Hashing Concept
key → hash_function(key) → index → store in array[index]

Example: hash(key) = key % table_size

Insert keys: 25, 37, 42, 55, 73  (table_size = 10)
  25 % 10 = 5  → slot 5
  37 % 10 = 7  → slot 7
  42 % 10 = 2  → slot 2
  55 % 10 = 5  → COLLISION! Slot 5 already has 25!
  73 % 10 = 3  → slot 3

Collision Resolution Techniques

2.3 Graphs — Vertices, Edges, Connections

Layer 1 — Intuition

A graph is a social network. Each person is a vertex, each friendship is an edge. Unlike trees, graphs can have cycles (A→B→C→A), disconnected components, and edges with weights (distance between cities).

Layer 2 — Representations

Example Graph
     A ——(4)—— B
     |         |
    (2)       (3)
     |         |
     C ——(1)—— D

Adjacency Matrix
     A  B  C  D
A  [ 0  4  2  0 ]
B  [ 4  0  0  3 ]
C  [ 2  0  0  1 ]
D  [ 0  3  1  0 ]
Space: O(V²). Good for dense graphs.

Adjacency List
A → [(B,4), (C,2)]
B → [(A,4), (D,3)]
C → [(A,2), (D,1)]
D → [(B,3), (C,1)]
Space: O(V+E). Good for sparse graphs.

BFS vs DFS

2.4 Shortest Path Algorithms

Dijkstra's Algorithm — Single Source Shortest Path

Graph: A-(4)-B, A-(2)-C, B-(3)-D, C-(1)-D

Step 0: dist = {A:0, B:∞, C:∞, D:∞}     visited = {}
Step 1: Visit A (dist=0)
        Update B: 0+4=4, C: 0+2=2
        dist = {A:0, B:4, C:2, D:∞}       visited = {A}
Step 2: Visit C (dist=2, smallest unvisited)
        Update D: 2+1=3
        dist = {A:0, B:4, C:2, D:3}       visited = {A,C}
Step 3: Visit D (dist=3)
        Update B: 3+3=6 > 4, no update
        dist = {A:0, B:4, C:2, D:3}       visited = {A,C,D}
Step 4: Visit B (dist=4)
        dist = {A:0, B:4, C:2, D:3}       visited = {A,C,D,B}

Shortest: A→B=4, A→C=2, A→D=3 (via C!)

Time: O((V+E) log V) with min-heap. Without heap: O(V²).

Floyd-Warshall — All-Pairs Shortest Path

Finds shortest path between every pair of vertices. Uses dynamic programming: "Can going through vertex k improve the path from i to j?"

Core Idea
for k in all vertices:
    for i in all vertices:
        for j in all vertices:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Time: O(V³)   Space: O(V²)
Used when: You need ALL shortest paths (e.g., IRCTC route planning between ALL station pairs).