# Heap / Priority Queue — Concept

[অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md)

> একটাই promise, সস্তায় রাখা: "সবচেয়ে important item টা সবসময় উপরে থাকবে।"

---

## Real-life analogy: hospital triage

একটা হাসপাতালের emergency room-এ ঢোকো। রোগীদের আসার order-এ চিকিৎসা হয় *না*। একজন nurse প্রতিটা রোগীকে একটা urgency score দেন, আর সবচেয়ে urgent রোগীকেই সবসময় আগে ডাকা হয় — সে এক মিনিট আগে এলেও, আর মচকানো গোড়ালি নিয়ে কেউ এক ঘণ্টা অপেক্ষা করলেও।

খেয়াল করো triage system টা কী *করে না*:

- সব রোগীর একটা পুরোপুরি sorted লাইন **রাখে না**। সেটা হতো শ্রমের অপচয় — order-এর বেশিরভাগ অংশই কখনো কাজে লাগে না।
- শুধু একটা জিনিসই guarantee করে: **পরের জনকে যাকে ডাকা হবে, সে-ই এখনকার সবচেয়ে urgent।**

এটাই ঠিক একটা priority queue। আর heap হলো সেই filing system যেটা দিয়ে nurse এই একটা promise সস্তায় রাখেন: একটা ঢিলেঢালা, partial ordering — যেটা ঠিক যতটুকু দরকার ততটুকুই strong।

*Shape*-এর জন্য দ্বিতীয় একটা analogy: একটা corporate tournament bracket, যেখানে প্রতিটা manager তার ঠিক নিচের দুজনের চেয়ে "বেশি urgent"। CEO (root) যে সবার মধ্যে সবচেয়ে urgent — সেটা সাথে সাথে জানো — কিন্তু আলাদা branch-এর দুটো random employee-র তুলনা কেমন, সেটা প্রায় কিছুই জানো না। Heap ইচ্ছে করেই এতটা vague থাকে, কারণ vagueness maintain করা সস্তা।

## Memory picture: array-র ভেতরে বাস করা একটা tree

Heap-কে fast বানানো surprise টা এখানে: "tree" টা আসলে একটা আঁকা ছবি, কোনো real structure না। কোনো node object নেই, কোনো pointer নেই। Heap হলো একটা সাধারণ array, আর tree shape টা **index math দিয়ে compute করা হয়**।

Heap সবসময় একটা **complete** binary tree: প্রতিটা level পূর্ণ, শুধু শেষেরটা ছাড়া — যেটা বাঁ থেকে ডানে fill হয়, কোনো ফাঁক ছাড়া। Completeness-ই array trick টাকে কাজ করায় — কোনো hole নেই, কোনো wasted slot নেই।

Index `i`-এর item-টার জন্য:

```text
left child   = 2*i + 1
right child  = 2*i + 2
parent       = (i - 1) // 2
```

7-টা item-এর একটা min-heap-এর উদাহরণ:

```text
Array:   index   0    1    2    3    4    5    6
         value [ 2 ,  5 ,  3 ,  9 ,  6 ,  8 ,  4 ]

Tree view (same data, just drawn):

                 2          <- index 0 (root, the minimum)
               /   \
             5       3      <- indices 1, 2
            / \     / \
           9   6   8   4    <- indices 3, 4, 5, 6
```

অঙ্কটা মিলিয়ে দেখো: index 1-এর (value 5) children হলো index `2*1+1 = 3` আর `2*1+2 = 4` — values 9 আর 6। Index 5-এর (value 8) parent হলো `(5-1)//2 = 2` — value 3। ছবিতে প্রতিটা parent-child রেখা আসলে array-র উপর শুধু arithmetic।

এটা কেন matter করে:

- **No pointers** মানে কম memory আর দারুণ cache behavior — পুরো tree টা একটা contiguous block।
- **Completeness** মানে height ঠিক `floor(log2 n)`। দশ লাখ item-এর একটা heap-ও মাত্র ~20 level লম্বা। Leaf থেকে root, বা root থেকে leaf — প্রতিটা হাঁটায় বড়জোর ~20-টা item ছোঁয়া লাগে। O(log n) এখান থেকেই আসে।

## Core invariant: heap property

> **Min-heap property:** প্রতিটা parent তার দুই child-এর চেয়ে ছোট অথবা সমান।

ব্যস, এটাই পুরো আইন। এর consequences:

- Root-টাই global minimum (যেকোনো path ধরে উপরে আইনটা follow করো: প্রতিটা step-এ value শুধু ছোট বা সমানই হতে পারে)।
- Siblings-দের মধ্যে **কোনো** guaranteed order নেই। উপরের ছবিতে 9 বসে আছে 6-এর *বাঁয়ে*, আর 5 বসে আছে 3-এর *level-এর নিচে* — দুটোই ঠিক আছে।
- Array টা sorted **না**। `[2, 5, 3, 9, 6, 8, 4]` একটা valid heap, আর স্পষ্টতই unsorted।

প্রতিটা heap operation আসলে "সস্তা কাজটা করো, তারপর property repair করো":

- **Push:** শেষে append করো (tree complete থাকে), তারপর *sift up* — parent-কে যতক্ষণ হারাচ্ছো, swap করতে থাকো।
- **Pop:** root save করো, *শেষ* item টাকে root slot-এ বসাও (tree complete থাকে), তারপর *sift down* — ছোট child-এর কাছে যতক্ষণ হারছো, swap করতে থাকো।

দুটো repair-ই একটা root-to-leaf path ধরে হাঁটে, তাই দুটোই O(log n)। Frame-by-frame ছবির জন্য [visual-explanation.md](visual-explanation.md) দেখো।

Max-heap হলো mirror image: প্রতিটা parent তার children-এর চেয়ে বড় বা সমান, আর root-টাই maximum।

## Heap কখন ব্যবহার করবে — আর কখন না

Heap ব্যবহার করো যখন:

- বারবার **শুধু extreme টা** (min বা max) দরকার, পুরো sorted order না।
- Extract করতে করতে items **আসতেই থাকে** — one-time sort সেটা handle করতে পারে না।
- বিশাল বা infinite একটা stream থেকে k best গুলো লাগবে, ছোট memory-তে।
- একটা greedy algorithm বলছে "সবসময় cheapest / earliest / heaviest টা পরে নাও।"

Heap ব্যবহার **করো না** যখন:

- Data একবারই পুরোপুরি sort করতে হবে আর কখনো insert হবে না — শুধু `sorted()` call করো, এটা simpler আর constants ভালো।
- Arbitrary value-র জন্য fast *search* দরকার — heap "42 কি এখানে আছে?" এটা O(n)-এর চেয়ে দ্রুত খুঁজতে পারে না। Hash set ব্যবহার করো ([../05-hashing/](../05-hashing/README.md))।
- Random access-এ *index* অনুযায়ী k-th smallest দরকার — sorted list বা selection algorithm বেশি মানানসই।
- প্রায়ই arbitrary middle elements delete করতে হবে — heap-এ তখন lazy-deletion trick লাগে (দেখো [patterns.md](patterns.md)) বা অন্য কোনো structure।

## Complexity table

| Operation | Heap | Sorted list | Unsorted list |
| --- | --- | --- | --- |
| Peek best | O(1) | O(1) | O(n) |
| Pop best | O(log n) | O(n) (shift) or O(1) (from end) | O(n) |
| Insert | O(log n) | O(n) | O(1) |
| Build from n items | O(n) with heapify | O(n log n) sort | O(1) |
| Search arbitrary value | O(n) | O(log n) | O(n) |
| Space | O(n) | O(n) | O(n) |

প্রথম তিন row-তে heap-ই একমাত্র column যেখানে কোনো O(n) নেই — এই balance-টাই এর অস্তিত্বের পুরো কারণ।

মনে রাখার মতো একটা surprising fact: **heapify O(n), O(n log n) না।** Intuition: অর্ধেক nodes হলো leaf, তাদের কোনো কাজই লাগে না; এক-চতুর্থাংশের লাগে বড়জোর 1-টা swap; এক-অষ্টমাংশের বড়জোর 2; শুধু একটা node-এর (root) লাগতে পারে log n। Weighted sum টা গুটিয়ে এসে দাঁড়ায় O(n)-এ। বেশিরভাগ node থাকে নিচের দিকে, যেখানে sift down প্রায় free।

## ছোট ছোট Python snippets, dry run সহ

### 1. `heapq` basics — push আর pop

```python
import heapq

h = []                  # a heap is just a list
heapq.heappush(h, 5)    # h = [5]
heapq.heappush(h, 2)    # h = [2, 5]        2 sifted up past 5
heapq.heappush(h, 8)    # h = [2, 5, 8]     8 stays, parent 2 is smaller
heapq.heappush(h, 1)    # h = [1, 2, 8, 5]  1 sifted up to the root

print(h[0])             # 1  -- peek: the min is ALWAYS at index 0
print(heapq.heappop(h)) # 1  -- h becomes [2, 5, 8]
print(heapq.heappop(h)) # 2  -- h becomes [5, 8]
```

শেষ push-টার dry run: index 3-এ 1 append করো। Parent হলো `(3-1)//2 = 1`, value 5। যেহেতু 1 < 5, swap — 1 এখন index 1-এ। Parent হলো `(1-1)//2 = 0`, value 2। যেহেতু 1 < 2, swap — 1 এখন root। 4-টা item-এর জন্য 2-টা swap-এই শেষ: এটাই log n কাজ করছে।

### 2. Negation দিয়ে max-heap

```python
import heapq

nums = [3, 1, 4, 1, 5]
h = [-x for x in nums]   # negate everything
heapq.heapify(h)         # O(n) build; h[0] == -5

biggest = -heapq.heappop(h)   # 5
second  = -heapq.heappop(h)   # 4
```

সবচেয়ে ছোট negative টাই সবচেয়ে বড় original। ঢোকার সময় একটা minus sign, বেরোনোর সময় আরেকটা।

### 3. Heapify, তারপর সব pop করো — spirit-এ heapsort

```python
import heapq

data = [9, 4, 7, 1, 3]
heapq.heapify(data)            # data = [1, 3, 7, 9, 4] -- valid heap, NOT sorted

out = [heapq.heappop(data) for _ in range(5)]
print(out)                     # [1, 3, 4, 7, 9] -- popping n times sorts
```

`heapify`-এর dry run: array-র মাঝখান থেকে পেছনের দিকে প্রতিটা non-leaf-কে sift down করে। Item 9 আর 3 হলো leaf (free)। Index 1 (value 4): children 1 আর 3, smallest child 1 হারিয়ে দেয় 4-কে, swap। Index 0 (value 9): smaller child এখন 1, swap; তারপর 9 vs children 4 আর 3, 3-এর সাথে swap। মোট: 5-টা item সাজাতে 3-টা swap।

### 4. Tuples — (priority, item) হিসেবে

```python
import heapq

tasks = []
heapq.heappush(tasks, (2, "write tests"))
heapq.heappush(tasks, (1, "fix prod bug"))
heapq.heappush(tasks, (3, "refactor"))

priority, task = heapq.heappop(tasks)
print(task)    # "fix prod bug" -- lowest number = most urgent
```

Python tuples-কে element by element compare করে, তাই প্রথম field-টাই priority হিসেবে কাজ করে। Pitfall: দুটো priority সমান হলে Python *দ্বিতীয়* field compare করে — items comparable না হলে crash। Real code একটা unique counter যোগ করে: `(priority, counter, item)`।

## পরের ধাপের সাথে bridge

- [visual-explanation.md](visual-explanation.md) sift-up আর sift-down frame by frame দেখায় — from-scratch implementation ছোঁয়ার আগে এটা পড়ো।
- [patterns.md](patterns.md) এই একটা structure-কে ছয়টা reusable problem-solving move-এ পরিণত করে।
- [../09-graphs/shortest-path.md](../09-graphs/shortest-path.md)-এর Dijkstra algorithm-এর ভেতরের engine হলো এই heap-ই — "সবসময় cheapest path expand করো" মানে আসলে "সবসময় heap pop করো।"