# 08 — Heap / Priority Queue

> **এখান থেকে শুরু করুন:** [সহজ ব্যাখ্যা, শেখার ক্রম ও বাস্তব ব্যবহার](learning-guide.md) → [প্রশ্ন, official link ও স্থানীয় সমাধান](problems/README.md)। [উৎসের তালিকা](source-map.md)-এ reference পাবেন।

> একটা 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](../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/](../02-arrays-and-strings/README.md))।
- Basic tree vocabulary: root, parent, child, leaf ([../07-trees/](../07-trees/README.md))।
- Big-O — অন্তত "O(log n) মানে অর্ধেক হতে থাকা" এই intuition level-এ।

## শেখার আগে কী revise করবে

- Complete binary tree কীভাবে level by level, বাঁ থেকে ডানে fill হয় ([../07-trees/concept.md](../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 কোনটা?" — বারবার উত্তর দিতে থাকো · [ব্যাখ্যা](problems/002-kth-largest-element-in-a-stream.md) | [LeetCode 703](https://leetcode.com/problems/kth-largest-element-in-a-stream/) | Top-K (size-k min-heap) |
| Last Stone Weight — দুটো সবচেয়ে ভারী পাথরকে বারবার একসাথে smash করো · [ব্যাখ্যা](problems/001-last-stone-weight.md) | [LeetCode 1046](https://leetcode.com/problems/last-stone-weight/) | Simulation (negation দিয়ে max-heap) |
| Relative Ranks — score order অনুযায়ী medal দাও · [ব্যাখ্যা](problems/003-relative-ranks.md) | [LeetCode 506](https://leetcode.com/problems/relative-ranks/) | Heap / sorting warm-up |
| Ferris Wheel — weight limit-এর মধ্যে বাচ্চাদের gondola-য় pair করো · [ব্যাখ্যা](problems/004-ferris-wheel.md) | [CSES 1090 · Ferris Wheel](https://cses.fi/problemset/task/1090) | Greedy + sorted ends (heap-ঘেঁষা thinking) |

### Medium

| Problem | Source | Pattern |
| --- | --- | --- |
| Kth Largest Element in an Array — পুরোপুরি sort না করে kth largest খুঁজে বের করো · [ব্যাখ্যা](problems/005-kth-largest-element-in-an-array.md) | [LeetCode 215](https://leetcode.com/problems/kth-largest-element-in-an-array/) | Top-K |
| Top K Frequent Elements — সবচেয়ে common k-টা value · [ব্যাখ্যা](problems/006-top-k-frequent-elements.md) | [LeetCode 347](https://leetcode.com/problems/top-k-frequent-elements/) | Top-K + hash counting (inherit করে [../05-hashing/](../05-hashing/README.md) থেকে) |
| K Closest Points to Origin — plane-এ k-টা nearest point · [ব্যাখ্যা](problems/007-k-closest-points-to-origin.md) | [LeetCode 973](https://leetcode.com/problems/k-closest-points-to-origin/) | Top-K (size k-এর max-heap) |
| Kth Smallest Element in a Sorted Matrix — rows আর columns দুটোই sorted · [ব্যাখ্যা](problems/012-kth-smallest-in-sorted-matrix.md) | [LeetCode 378](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/) | K-way merge |
| Meeting Rooms II — minimum কয়টা room লাগবে যেন কোনো meeting overlap না করে · [ব্যাখ্যা](problems/009-meeting-rooms-ii.md) | [LeetCode 253](https://leetcode.com/problems/meeting-rooms-ii/) | Earliest end দিয়ে scheduling |
| Task Scheduler — repeat-এর মাঝে cooldown রেখে task order করো · [ব্যাখ্যা](problems/010-task-scheduler.md) | [LeetCode 621](https://leetcode.com/problems/task-scheduler/) | Heap + greedy |
| Reorganize String — অক্ষরগুলো এমনভাবে সাজাও যেন দুটো একই অক্ষর পাশাপাশি না বসে · [ব্যাখ্যা](problems/011-reorganize-string.md) | [LeetCode 767](https://leetcode.com/problems/reorganize-string/) | Heap + greedy (most frequent আগে) |
| Single-Threaded CPU — একটা CPU simulate করো যেটা shortest available job বেছে নেয় · [ব্যাখ্যা](problems/013-single-threaded-cpu.md) | [LeetCode 1834](https://leetcode.com/problems/single-threaded-cpu/) | Scheduling / simulation |
| Furthest Building You Can Reach — সবচেয়ে বড় climb-গুলোতে ladder খরচ করো · [ব্যাখ্যা](problems/014-furthest-building-you-can-reach.md) | [LeetCode 1642](https://leetcode.com/problems/furthest-building-you-can-reach/) | Heap + greedy |
| Concert Tickets — প্রতিটা customer তার budget-এর মধ্যে সবচেয়ে দামি ticket টা নেয় · [ব্যাখ্যা](problems/015-concert-tickets.md) | [CSES 1091 · Concert Tickets](https://cses.fi/problemset/task/1091) | Ordered structure / multiset thinking |

### Hard

| Problem | Source | Pattern |
| --- | --- | --- |
| Merge k Sorted Lists — k-টা sorted linked list-কে একটায় combine করো · [ব্যাখ্যা](problems/017-merge-k-sorted-lists.md) | [LeetCode 23](https://leetcode.com/problems/merge-k-sorted-lists/) | K-way merge |
| Find Median from Data Stream — numbers আসতে আসতে running median বের করো · [ব্যাখ্যা](problems/018-find-median-from-data-stream.md) | [LeetCode 295](https://leetcode.com/problems/find-median-from-data-stream/) | Two heaps |
| Sliding Window Median — size k-এর প্রতিটা window-র median · [ব্যাখ্যা](problems/021-sliding-window-median.md) | [LeetCode 480](https://leetcode.com/problems/sliding-window-median/) | Two heaps + lazy deletion |
| Smallest Range Covering Elements from K Lists — প্রতিটা list ছুঁয়ে যাওয়া সবচেয়ে tight interval · [ব্যাখ্যা](problems/020-smallest-range-k-lists.md) | [LeetCode 632](https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/) | K-way merge |
| IPO — final capital maximize করতে বড়জোর k-টা project বাছো · [ব্যাখ্যা](problems/019-ipo.md) | [LeetCode 502](https://leetcode.com/problems/ipo/) | Two heaps + greedy |
| Trapping Rain Water II — 3D version: একটা height map-এর উপর কতটা পানি জমে · [ব্যাখ্যা](problems/022-trapping-rain-water-ii.md) | [LeetCode 407](https://leetcode.com/problems/trapping-rain-water-ii/) | 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](https://visualgo.net/en)-তে interactive heap টা explore করো (Binary Heap module)।
- [visual-explanation.md](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

1. [concept.md](concept.md) — analogy, array-as-tree memory picture, heap property, complexity।
2. [visual-explanation.md](visual-explanation.md) — push আর pop, frame by frame।
3. [patterns.md](patterns.md) — ছয়টা named heap pattern, thinking tweak সহ।
4. [implementation.py](implementation.py) — পড়ো, run করো, ভাঙো, ঠিক করো।
5. [problems/README.md](problems/README.md) — tracker শুরু করো আর easy থেকে hard পর্যন্ত grind করো।

## Source map

এই folder-এর প্রতিটা idea আর link কোথা থেকে এসেছে এবং প্রত্যেকটার copying status কী — তার জন্য দেখো [source-map.md](./source-map.md)।