08 — Heap / Priority Queue¶
একটা waiting room ভাবো যেখানে সবচেয়ে জরুরি case-টাকে সবসময় আগে ডাকা হয় — সে কখন এসেছে সেটা ব্যাপার না।
এই data structure টা কী¶
Heap হলো একটা complete binary tree যেটা একটা সাধারণ array-র ভেতরে থাকে, আর এমনভাবে সাজানো যে সবচেয়ে important item টা সবসময় root-এ (index 0) বসে থাকে। Min-heap সবচেয়ে ছোট item কে উপরে রাখে; max-heap রাখে সবচেয়ে বড়টাকে।
Priority queue হলো abstract idea-টা: "আমাকে পরের best item টা দাও।" Heap হলো সেই idea implement করার সবচেয়ে common machine। Python-এ standard library-র heapq module যেকোনো list-কে min-heap বানিয়ে দেয়।
Magic trick-টা হলো: পুরো tree-টা কখনোই sorted অবস্থায় দেখবে না। Heap শুধু একটাই promise করে — উপরেরটাই best — আর এই একটা promise-ই কয়েক ডজন algorithm চালানোর জন্য যথেষ্ট।
এটা কেন আছে (কোন pain solve করে)¶
ধরো, একটা changing collection থেকে বারবার সবচেয়ে ছোট number টা তুলে নিতে হবে।
- Sorted list "smallest?" এর উত্তর দেয় O(1)-এ, কিন্তু নতুন number insert করতে O(n) লাগে sorted রাখার জন্য।
- Unsorted list insert করে O(1)-এ, কিন্তু smallest খুঁজতে প্রতিবার O(n) খরচ হয়।
দুটো operation-ই যখন অনেকবার করতে হয়, তখন দুটোই fail করে। Heap হলো সেই compromise যেটা জিতে যায়:
- Insert: O(log n)
- Best টা remove করা: O(log n)
- Best টা peek করা: O(1)
কোনো problem যখনই বলে "বারবার smallest / largest / earliest / cheapest টা নাও", তখন heap একটা O(n^2) solution-কে O(n log n) বানিয়ে দেয়।
Real software-এ কোথায় ব্যবহার হয়¶
- Operating system scheduler — highest-priority process টা পরে run হয়।
- Dijkstra-র shortest path — সবসময় cheapest known route টা expand করা হয় (দেখো
../09-graphs/shortest-path.md)। - Heapsort — heap থেকে বারবার pop করে sort করা।
- Event simulator আর game engine — সবচেয়ে আগের timestamp-ওয়ালা event টা process করা।
- Streaming "top K" — trending hashtags, top sellers, hottest posts — limited memory-তে।
- Network server-এর timer — যে timer সবার আগে expire করবে সেটা fire করা।
- Compression-এ Huffman coding — বারবার দুটো least frequent symbol merge করা।
Prerequisites¶
- Python-এ স্বাচ্ছন্দ্য: lists, functions, classes, tuples।
- Arrays আর index arithmetic (
../02-arrays-and-strings/)। - Basic tree vocabulary: root, parent, child, leaf (
../07-trees/)। - Big-O — অন্তত "O(log n) মানে অর্ধেক হতে থাকা" এই intuition level-এ।
শেখার আগে কী revise করবে¶
- Complete binary tree কীভাবে level by level, বাঁ থেকে ডানে fill হয় (
../07-trees/concept.md)। - Integer division:
(i - 1) // 2— এই একটা formula-ই heap-এর কঙ্কাল। - n nodes-এর একটা balanced tree-র height কেন প্রায় log2(n)।
- Python-এ tuple comparison:
(2, 'b') < (3, 'a')element by element compare করে — tuples-এর heap এটার উপরেই দাঁড়িয়ে।
Learning goals (checklist)¶
- [ ] Heap property এক লাইনে explain করতে পারা (parent দুই child-কেই হারায়)।
- [ ] Notes না দেখে
2i+1,2i+2,(i-1)//2দিয়ে tree picture আর array indices-এর মধ্যে convert করতে পারা। - [ ] কাগজে একটা push (sift-up) আর একটা pop (sift-down), frame by frame trace করতে পারা।
- [ ] Push আর pop কেন O(log n) আর peek কেন O(1) — explain করতে পারা।
- [ ]
heapq.heappush,heappop,heapify, আর max-heap-এর জন্য negate trick ব্যবহার করতে পারা। - [ ] Size k-এর heap দিয়ে একটা top-K problem solve করা, আর সেটা কেন min-heap তা explain করতে পারা।
- [ ] k-টা cursor-ওয়ালা একটা heap দিয়ে k sorted lists merge করতে পারা।
- [ ] দুটো heap দিয়ে running median maintain করতে পারা।
- [ ] "remove arbitrary item"-এর কষ্ট থেকে lazy deletion কখন বাঁচায় — চিনতে পারা।
- [ ]
heapifyদিয়ে heap বানানো কেন O(n), O(n log n) না — explain করতে পারা।
Problem categories¶
| Category | Typical question shape |
|---|---|
| Top-K | "Find the k largest / smallest / most frequent / closest" |
| K-way merge | "Merge k sorted lists / find smallest range across lists" |
| Two heaps | "Running median", "balance two halves of a stream" |
| Scheduling / greedy | "Minimum rooms / machines / cost when processing jobs" |
| Simulation | "Repeatedly combine two smallest / smash two largest" |
| Lazy deletion | "Sliding window max-min with removals", "stale entries" |
| Heap + graph | "Cheapest path first" — Dijkstra, Prim |
Practice list¶
নিচের সব problem আমাদের নিজের ভাষায় describe করা; official statement-এর জন্য link follow করো। Difficulty labels মোটামুটি আনুমানিক।
Easy¶
| Problem | Source | Pattern |
|---|---|---|
| Kth Largest Element in a Stream — "এখন পর্যন্ত kth largest কোনটা?" — বারবার উত্তর দিতে থাকো | LeetCode 703 | Top-K (size-k min-heap) |
| Last Stone Weight — দুটো সবচেয়ে ভারী পাথরকে বারবার একসাথে smash করো | LeetCode 1046 | Simulation (negation দিয়ে max-heap) |
| Relative Ranks — score order অনুযায়ী medal দাও | LeetCode 506 | Heap / sorting warm-up |
| Ferris Wheel — weight limit-এর মধ্যে বাচ্চাদের gondola-য় pair করো | CSES Problem Set — "Ferris Wheel" | Greedy + sorted ends (heap-ঘেঁষা thinking) |
Medium¶
| Problem | Source | Pattern |
|---|---|---|
| Kth Largest Element in an Array — পুরোপুরি sort না করে kth largest খুঁজে বের করো | LeetCode 215 | Top-K |
| Top K Frequent Elements — সবচেয়ে common k-টা value | LeetCode 347 | Top-K + hash counting (inherit করে ../05-hashing/ থেকে) |
| K Closest Points to Origin — plane-এ k-টা nearest point | LeetCode 973 | Top-K (size k-এর max-heap) |
| Kth Smallest Element in a Sorted Matrix — rows আর columns দুটোই sorted | LeetCode 378 | K-way merge |
| Meeting Rooms II — minimum কয়টা room লাগবে যেন কোনো meeting overlap না করে | LeetCode 253 | Earliest end দিয়ে scheduling |
| Task Scheduler — repeat-এর মাঝে cooldown রেখে task order করো | LeetCode 621 | Heap + greedy |
| Reorganize String — অক্ষরগুলো এমনভাবে সাজাও যেন দুটো একই অক্ষর পাশাপাশি না বসে | LeetCode 767 | Heap + greedy (most frequent আগে) |
| Single-Threaded CPU — একটা CPU simulate করো যেটা shortest available job বেছে নেয় | LeetCode 1834 | Scheduling / simulation |
| Furthest Building You Can Reach — সবচেয়ে বড় climb-গুলোতে ladder খরচ করো | LeetCode 1642 | Heap + greedy |
| Concert Tickets — প্রতিটা customer তার budget-এর মধ্যে সবচেয়ে দামি ticket টা নেয় | CSES Problem Set — "Concert Tickets" | Ordered structure / multiset thinking |
Hard¶
| Problem | Source | Pattern |
|---|---|---|
| Merge k Sorted Lists — k-টা sorted linked list-কে একটায় combine করো | LeetCode 23 | K-way merge |
| Find Median from Data Stream — numbers আসতে আসতে running median বের করো | LeetCode 295 | Two heaps |
| Sliding Window Median — size k-এর প্রতিটা window-র median | LeetCode 480 | Two heaps + lazy deletion |
| Smallest Range Covering Elements from K Lists — প্রতিটা list ছুঁয়ে যাওয়া সবচেয়ে tight interval | LeetCode 632 | K-way merge |
| IPO — final capital maximize করতে বড়জোর k-টা project বাছো | LeetCode 502 | Two heaps + greedy |
| Trapping Rain Water II — 3D version: একটা height map-এর উপর কতটা পানি জমে | LeetCode 407 | Heap + border থেকে BFS |
Visualization ideas¶
- প্রতিটা operation-এর জন্য heap-টা দুবার আঁকো: একবার tree হিসেবে, একবার underlying array হিসেবে। দেখো দুটো কীভাবে sync-এ থাকে।
- Sift-up-কে animate করো একটা bubble উপরে ওঠার মতো; sift-down-কে একটা পাথর ডুবে যাওয়ার মতো — যেটা হালকা child-টাকে বেছে নিয়ে swap করে।
- Top-K-র জন্য একটা velvet rope আঁকো: size-k min-heap টা হলো bouncer — newcomer-কে club-এ ঢুকতে হলে সবচেয়ে দুর্বল member-কে হারাতে হবে।
- Two heaps-এর জন্য একটা seesaw আঁকো: বাঁয়ে max-heap (lower half), ডানে min-heap (upper half), pivot-এ median।
- VisuAlgo-তে interactive heap টা explore করো (Binary Heap module)।
visual-explanation.md-র প্রতিটা frame pencil আর কাগজ দিয়ে আবার trace করো।
Common mistakes (সাধারণ ভুল)¶
- ভুলে যাওয়া যে
heapqশুধুই min-heap — max-heap লাগলে negated values push করো আর pop-এ আবার negate করো। - এমন tuples push করা যাদের second elements comparable না (যেমন দুটো dict) — tie হলে Python crash করে। Tie-breaker হিসেবে একটা unique counter যোগ করো:
(priority, counter, item)। heap[k]call করে sorted order আশা করা — শুধুheap[0]-ই guaranteed; বাকিটা মোটেই sorted না।heapq-র আড়ালে list-টা mutate করা (sort করা, মাঝখান থেকে delete করা) — heap property নিঃশব্দে ভেঙে যায়।- যেখানে existing list-এ
heapq.heapify(O(n)) যথেষ্ট, সেখানে n বারheapq.heappush(O(n log n)) call করা। - Top-K-তে সব n items-এর একটা max-heap ব্যবহার করা (O(n log n), memory-ভারী) — size k-এর min-heap (O(n log k))-এর বদলে।
- Lazy deletion ভুলে যাওয়া: মাঝখানের একটা element সরাসরি remove করা O(n); সেটাকে stale mark করে pop-এর সময় skip করা amortized O(log n)।
Interview problems-এর সাথে connection¶
Big-tech interview preparation-এর জন্য heap হলো highest-yield structure-গুলোর একটা। "k largest", "k closest", "most frequent", "merge k", আর "running median" — এই phrase-গুলো কার্যত জ্বলজ্বলে sign যেগুলো বলে heap। Interviewer-রা top-K pattern টা ভালোবাসে কারণ elegant solution-টা (size k-এর একটা min-heap) naive instinct-এর (সবকিছুর একটা max-heap) ঠিক উল্টো — এই inversion টা মুখে explain করতে পারা মানেই real understanding দেখানো।
Competitive programming-এর সাথে connection¶
heapqদিয়ে Dijkstra হলো Codeforces আর CSES-এর bread-and-butter shortest-path tool।- Greedy + heap মিলে scheduling আর "বারবার extremes নাও" ধাঁচের বিশাল একটা problem family solve করে।
- Python-এ ordered multiset নেই — lazy deletion সেটার substitute।
- Huffman-style "দুটো smallest merge করো" cost-minimization problem-এ দেখা যায়।
heapifyযে O(n), এটা matter করে যখন n হলো 10^6 আর time limit tight।
Recommended learning order¶
concept.md— analogy, array-as-tree memory picture, heap property, complexity।visual-explanation.md— push আর pop, frame by frame।patterns.md— ছয়টা named heap pattern, thinking tweak সহ।implementation.py— পড়ো, run করো, ভাঙো, ঠিক করো।problems/README.md— tracker শুরু করো আর easy থেকে hard পর্যন্ত grind করো।
Source map¶
এই folder-এর প্রতিটা idea আর link কোথা থেকে এসেছে এবং প্রত্যেকটার copying status কী — তার জন্য দেখো source-map.md।