# Heap: বারবার সেরা প্রার্থীটি নেওয়া

[অধ্যায়ের সূচি](README.md) · [অনুশীলন ও সমাধান](problems/README.md) · [মূল ধারণা](concept.md)

Heap-এর কাজ সব item সাজিয়ে রাখা নয়। কাজ হলো **এখন সবচেয়ে ছোট বা সবচেয়ে বড় কোনটি**, সেই প্রশ্নের উত্তর দ্রুত দেওয়া। নতুন item আসবে, সেরা item বের হবে, আবার নতুন item আসবে—এই ধরনের প্রোগ্রামে heap কাজে লাগে।

## শেখার ক্রম

| ধাপ | লিংক | ছোট লক্ষ্য |
| --- | --- | --- |
| 1 | [Heap property ও array index](concept.md) | parent ও child-এর index বের করা |
| 2 | [Push/pop-এর প্রতিটি frame](visual-explanation.md) | কোন swap-এর পরে property ঠিক হলো বোঝা |
| 3 | [Top-k, merge, two-heaps](patterns.md) | heap-এ ঠিক কী রাখবেন লিখতে পারা |
| 4 | [Python implementation](implementation.py) | duplicate ও খালি input সামলানো |
| 5 | [মূল প্রশ্ন + স্থানীয় নোট](problems/README.md) | একই pattern-এর দুই problem মিলিয়ে দেখা |

## একটি প্রোগ্রাম: deadline অনুযায়ী job চালানো

ধরি তিনটি কাজের deadline যথাক্রমে 9, 4 ও 7। Deadline যত ছোট, কাজ তত আগে চলবে। একই deadline হলে insertion counter দিয়ে নির্দিষ্ট ক্রম রাখা যায়।

```mermaid
flowchart TD
  A["(4, 1, email)"] --> B["(9, 0, backup)"]
  A --> C["(7, 2, report)"]
```

```python
import heapq

jobs = [(9, 0, "backup"), (4, 1, "email"), (7, 2, "report")]
heapq.heapify(jobs)
order = []
while jobs:
    deadline, sequence, name = heapq.heappop(jobs)
    order.append(name)
assert order == ["email", "report", "backup"]
```

| Operation | Heap-এ থাকা deadline-গুলো | ফল |
| --- | --- | --- |
| heapify | 4, 9, 7 | Root হলো 4 |
| pop | 7, 9 | email চালু |
| pop | 9 | report চালু |
| pop | খালি | backup চালু |

Heap-এর array `[4,9,7]` পুরো sorted নয়। কিন্তু root 4 হওয়ার নিশ্চয়তা আছে। `heapify` সময় `O(n)`; প্রতিটি pop সময় `O(log n)`। Job বাতিল বা priority বদলানোর দরকার হলে শুধু এই code যথেষ্ট নয়; [lazy deletion pattern](patterns.md) পড়ুন।

## Largest k-এর জন্য min-heap কেন

Stream `5,2,9,1,7` থেকে বড় 3টি সংখ্যা চাই। রাখা প্রার্থীদের **সবচেয়ে ছোটটি** নতুন বড় value এলে বাদ যাবে, তাই min-heap। নিচের তালিকাগুলো পড়ার সুবিধায় sorted; এগুলো heap-এর নির্দিষ্ট internal array layout দাবি করছে না।

| নতুন value | রাখা 3টি প্রার্থী | সিদ্ধান্ত |
| --- | --- | --- |
| 5 | [5] | জায়গা আছে |
| 2 | [2,5] | জায়গা আছে |
| 9 | [2,5,9] | জায়গা আছে |
| 1 | [2,5,9] | 1 রাখা প্রার্থীদের minimum 2-এর চেয়েও ছোট |
| 7 | [5,7,9] | 2 বাদ, 7 যোগ |

এখন root 5 হলো তৃতীয় বৃহত্তম। সব input sort না করেও `O(n log k)` সময় ও `O(k)` space-এ কাজ হলো।

## কোন কাজে কোন structure

| প্রয়োজন | বেছে নিন | কারণ |
| --- | --- | --- |
| নতুন event আসছে, পরের earliest event চাই | Min-heap | প্রতিবার minimum |
| অনেক sorted log stream একসঙ্গে পড়া | প্রতি stream-এর একটি head নিয়ে heap | সব log একসঙ্গে memory-তে লাগে না |
| চলমান stream-এর median | Max-heap + min-heap | দুই অর্ধের boundary দরকার |
| একবার সব item সাজানো | Sort | Heap প্রয়োজন নাও হতে পারে |
| Budget-এর নিচে সর্বোচ্চ ticket price | Ordered structure | সাধারণ heap arbitrary predecessor দেয় না |

শেষ row-টির অনুশীলন [Concert Tickets](problems/015-concert-tickets.md)। একটি অধ্যায়ে সমস্যা থাকলেই তার সেরা সমাধান সেই অধ্যায়ের data structure দিয়ে হবে—এমন ধরে নেবেন না।