Lesson 3 — Intermediate

Heap / Priority Queue

Heap ek special tree hai jisme root hamesha minimum (min-heap) ya maximum (max-heap) hota hai. Iska use top-k problems, scheduling, aur real-time data mein hota hai jahan tumhe fastest access chahiye.

Heap Data Structure Kya Hai?

Heap ek complete binary tree hai jo heap property satisfy karta hai:

• Min-Heap: Har parent node apne children se chota ya equal hai. Root = minimum element.
• Max-Heap: Har parent node apne children se bada ya equal hai. Root = maximum element.

Heap ko array mein store karna easy hai — koi pointer ki zaroorat nahi. Agar index i pe node hai toh:

• Left child = 2*i + 1
• Right child = 2*i + 2
• Parent = (i-1) // 2

Visual: Heap as Tree and Array

Min-Heap Tree: Array Representation:
 1 [1, 3, 5, 7, 9, 8, 6]
 / \ 0 1 2 3 4 5 6
 3 5
 / \ / \ Index mapping:
 7 9 8 6 Parent(1) = 0 ? 1
 Left(0) = 1 ? 3
 Right(0) = 2 ? 5
 Parent(3) = 1 ? 3
 Left(1) = 3 ? 7
 Right(1) = 4 ? 9

Heap property: Parent = Children (for min-heap)
Root (index 0) = minimum element = 1

Heapify Operation

Heapify ek operation hai jo ek node ko uski sahi position pe le jaata hai. Agar ek node apne children se bada hai (min-heap mein), toh usse neeche push karo — swap with smaller child.

Build Heap: Array se heap banana hai toh last non-leaf node se shuru karo aur har node ko heapify karo. Time: O(n) — not O(n log n)!

Push: Naya element end mein daalo aur up heapify karo (parent se compare karo, swap if needed).

Pop: Root nikalo, last element ko root pe daalo aur down heapify karo (children se compare karo, swap with smaller).

Heap Sort

Heap sort mein pehle max-heap banao, phir root (maximum) ko last position pe swap karo, heap size reduce karo, aur repeat karo. Yeh in-place sorting hai — O(n log n) time, O(1) space.

Lekin practical mein heap sort kam use hota hai kyunki merge sort aur quicksort zyada cache-friendly hain.

Top-K Problems

Heap ka sabse common use case hai "k largest ya k smallest elements find karna". Approach:

• K smallest: Max-heap use karo size k ka. Elements iterate karo, agar heap size > k hai toh root pop karo. End mein heap mein k smallest hongi.
• K largest: Min-heap use karo size k ka. Same logic — agar element bada hai root se toh push karo aur root pop karo.

Time: O(n log k) — heap mein sirf k elements rakte hain.

Code: Python heapq

import heapq

# Min-heap operations
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
print(heapq.heappop(heap)) # 1 (minimum)
print(heapq.heappop(heap)) # 3
print(heapq.heappop(heap)) # 5

# Max-heap trick: negate values
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -3)
print(-heapq.heappop(max_heap)) # 5 (maximum)

# K smallest elements
nums = [7, 10, 4, 3, 20, 15]
k = 3
print(heapq.nsmallest(k, nums)) # [3, 7, 10]

# K largest elements
print(heapq.nlargest(k, nums)) # [20, 15, 10]

# Build heap from array in O(n)
arr = [7, 10, 4, 3, 20, 15]
heapq.heapify(arr) # arr ab heap hai

Code: Kth Largest Element

def find_kth_largest(nums, k):
 # Min-heap of size k maintain karo
 min_heap = []

 for num in nums:
 heapq.heappush(min_heap, num)
 if len(min_heap) > k:
 heapq.heappop(min_heap)

 # Root = kth largest element
 return min_heap[0]


# Example
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2)) # 5
print(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) # 4

Median of Stream

Real-time data stream se median find karna classic heap problem hai. Approach: Do heaps use karo — max-heap for lower half, min-heap for upper half.

• Max-heap mein chote elements rakho (size = n/2 ya n/2+1)
• Min-heap mein bade elements rakho
• Median = max-heap root (odd count) ya (max-heap root + min-heap root) / 2 (even count)

Try it: code khud likho

Common Mistakes

• Max-heap banana bhoolna — Python mein sirf min-heap hai. Max-heap ke liye values negate karo (-val). Pop ke baad wapas negate karo.
• Heapify ka time complexity galat samajhna — heapify() O(n) hai, O(n log n) nahi. Ye bottom-up approach use karta hai.
• Heap size manage na karna — Top-k problems mein heap size k se zyada na hone do. Har push ke baad size check karo.
• Empty heap se pop karna — heappop se pehle check karo ki heap empty nahi hai. Error aayega nahi toh.
• Heap sort practical mein use karna — Interview mein heap sort mat likho sorting ke liye. Merge sort ya quicksort better hai. Heap sirf priority queue ke liye use karo.