Unit 5: Heaps, Hashing & Graphs

Python
class MaxHeap:
    """Max-Heap using array. Parent ≥ both children.
    Industry: Ola's driver pool — extract nearest (max priority) in O(1)."""
    def __init__(self):
        self.heap = []

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i):   return 2 * i + 1
    def _right(self, i):  return 2 * i + 2

    def insert(self, val):
        """Add value, then bubble UP. O(log n)."""
        self.heap.append(val)
        i = len(self.heap) - 1
        while i > 0 and self.heap[self._parent(i)] < self.heap[i]:
            p = self._parent(i)
            self.heap[i], self.heap[p] = self.heap[p], self.heap[i]
            i = p

    def extract_max(self):
        """Remove and return max (root). O(log n)."""
        if not self.heap: return None
        max_val = self.heap[0]
        self.heap[0] = self.heap[-1]    # Move last to root
        self.heap.pop()
        self._heapify_down(0)           # Bubble down
        return max_val

    def _heapify_down(self, i):
        """Restore heap property by bubbling down."""
        n = len(self.heap)
        largest = i
        l, r = self._left(i), self._right(i)
        if l < n and self.heap[l] > self.heap[largest]: largest = l
        if r < n and self.heap[r] > self.heap[largest]: largest = r
        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self._heapify_down(largest)


def heap_sort(arr):
    """HeapSort: Build max-heap, repeatedly extract max. O(n log n)."""
    n = len(arr)
    # Build max-heap (bottom-up) — O(n)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]   # Move max to end
        heapify(arr, i, 0)                # Heapify reduced array

def heapify(arr, n, i):
    largest = i
    l, r = 2*i+1, 2*i+2
    if l < n and arr[l] > arr[largest]: largest = l
    if r < n and arr[r] > arr[largest]: largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

data = [12, 11, 13, 5, 6, 7]
heap_sort(data)
print("HeapSort:", data)

C — HeapSort

C
#include <stdio.h>
void swap(int* a, int* b) { int t=*a; *a=*b; *b=t; }

void heapify(int a[], int n, int i) {
    int big=i, l=2*i+1, r=2*i+2;
    if(l<n && a[l]>a[big]) big=l;
    if(r<n && a[r]>a[big]) big=r;
    if(big!=i){ swap(&a[i],&a[big]); heapify(a,n,big); }
}
void heapSort(int a[], int n) {
    for(int i=n/2-1;i>=0;i--) heapify(a,n,i);
    for(int i=n-1;i>0;i--){ swap(&a[0],&a[i]); heapify(a,i,0); }
}
int main() {
    int a[]={12,11,13,5,6,7};
    heapSort(a,6);
    for(int i=0;i<6;i++) printf("%d ",a[i]);
    return 0;
}

Python
class HashTable:
    """Hash table with separate chaining (linked list per bucket).
    Industry: PhonePe checks transaction uniqueness in O(1)."""
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]  # Array of lists
        self.count = 0

    def _hash(self, key):
        return hash(key) % self.size

    def put(self, key, value):
        """Insert or update key-value pair. O(1) average."""
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)  # Update
                return
        self.table[idx].append((key, value))       # New entry
        self.count += 1

    def get(self, key):
        """Retrieve value by key. O(1) average."""
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key: return v
        return None

    def delete(self, key):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx].pop(i)
                self.count -= 1; return True
        return False

    def display(self):
        for i, bucket in enumerate(self.table):
            if bucket:
                print(f"  [{i}]: {' → '.join(f'{k}:{v}' for k,v in bucket)}")


ht = HashTable(7)
ht.put("TXN001", 500)
ht.put("TXN002", 1200)
ht.put("TXN003", 300)
ht.put("TXN004", 750)
print("Hash Table:"); ht.display()
print(f"Get TXN002: ₹{ht.get('TXN002')}")
ht.delete("TXN003")
print(f"After deleting TXN003: {ht.get('TXN003')}")

Python
from collections import deque

class Graph:
    """Graph using adjacency list representation."""
    def __init__(self):
        self.adj = {}   # {vertex: [neighbors]}

    def add_edge(self, u, v):
        self.adj.setdefault(u, []).append(v)
        self.adj.setdefault(v, []).append(u)  # Undirected

    def bfs(self, start):
        """Breadth-First Search using queue. O(V+E).
        Visits vertices level by level — finds shortest path (unweighted).
        Industry: Google Maps 'how many stops to destination?'"""
        visited = set([start])
        queue = deque([start])
        order = []

        while queue:
            vertex = queue.popleft()       # FIFO — visit oldest first
            order.append(vertex)
            for neighbor in self.adj.get(vertex, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

        return order

    def dfs(self, start, visited=None):
        """Depth-First Search using recursion. O(V+E).
        Goes deep before backtracking — detects cycles, topological sort.
        Industry: Web crawler follows links as deep as possible."""
        if visited is None: visited = set()
        visited.add(start)
        result = [start]
        for neighbor in self.adj.get(start, []):
            if neighbor not in visited:
                result.extend(self.dfs(neighbor, visited))
        return result


g = Graph()
for u, v in [("Delhi","Jaipur"), ("Delhi","Agra"), ("Jaipur","Udaipur"),
             ("Agra","Lucknow"), ("Lucknow","Varanasi")]:
    g.add_edge(u, v)

print("BFS from Delhi:", g.bfs("Delhi"))
print("DFS from Delhi:", g.dfs("Delhi"))

C — BFS

C
#include <stdio.h>
#define V 6

int adj[V][V], visited[V], queue[V], front=0, rear=-1;

void bfs(int start) {
    visited[start] = 1; queue[++rear] = start;
    while(front <= rear) {
        int v = queue[front++];
        printf("%d ", v);
        for(int i=0;i<V;i++)
            if(adj[v][i] && !visited[i]) { visited[i]=1; queue[++rear]=i; }
    }
}

int main() {
    adj[0][1]=adj[1][0]=1; adj[0][2]=adj[2][0]=1;
    adj[1][3]=adj[3][1]=1; adj[2][4]=adj[4][2]=1; adj[4][5]=adj[5][4]=1;
    printf("BFS: "); bfs(0);
    return 0;
}

Python
import heapq

def dijkstra(graph, start):
    """Dijkstra's algorithm using min-heap (priority queue).
    Finds shortest distance from start to ALL other vertices.
    Time: O((V+E) log V) with heap. Without: O(V²).
    
    Industry: Google Maps finds shortest route from your location
    to destination. IRCTC finds optimal train routes."""
    
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    prev = {v: None for v in graph}    # To reconstruct path
    pq = [(0, start)]                    # (distance, vertex)
    visited = set()
    
    while pq:
        d, u = heapq.heappop(pq)          # Get nearest unvisited
        if u in visited: continue
        visited.add(u)
        
        for v, weight in graph[u]:
            new_dist = d + weight
            if new_dist < dist[v]:
                dist[v] = new_dist        # Found shorter path!
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))
    
    return dist, prev


def get_path(prev, target):
    path = []
    while target:
        path.append(target)
        target = prev[target]
    return path[::-1]


# Indian railway network (simplified)
railway = {
    "Delhi":     [("Jaipur", 281), ("Agra", 200), ("Lucknow", 500)],
    "Jaipur":    [("Delhi", 281), ("Ahmedabad", 625)],
    "Agra":      [("Delhi", 200), ("Lucknow", 335)],
    "Lucknow":   [("Delhi", 500), ("Agra", 335), ("Varanasi", 300)],
    "Ahmedabad": [("Jaipur", 625), ("Mumbai", 524)],
    "Varanasi":  [("Lucknow", 300)],
    "Mumbai":    [("Ahmedabad", 524)],
}

dist, prev = dijkstra(railway, "Delhi")
print("=== IRCTC Route Planner: Delhi to All Cities ===")
for city, d in sorted(dist.items(), key=lambda x: x[1]):
    path = get_path(prev, city)
    print(f"  {city:12s}: {d:4d} km  via {' → '.join(path)}")