# Heap Patterns

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

> ছয়টা reusable thinking move। প্রত্যেকটার *trigger words* শিখে নাও — একটা problem কোন pattern-এর পোশাক পরে আছে সেটা চিনে ফেলাই অর্ধেক যুদ্ধ জেতা।

---

## Pattern 1 — Size-k heap দিয়ে Top-K

**Trigger words:** "k largest", "k smallest", "k most frequent", "k closest", "kth largest in a stream"।

**Core idea:** k-টা *largest* item খুঁজতে হলে একটা **size k-এর min-heap** রাখো। প্রতিটা newcomer লড়াই করে *বর্তমান সবচেয়ে ছোট member*-এর সাথে (heap top)। তাকে হারালে তুমি তার জায়গা নাও; হারলে তুমি rejected।

**Thinking tweak:** min-heap টা **top-K club-এর দরজা পাহারা দেয়**। সবচেয়ে দুর্বল member দরজায় দাঁড়িয়ে। Newcomer-কে সব k-জন member-এর সাথে compare করতে হয় না — শুধু দুর্বলতমের সাথে। Beginners এই counterintuitive অংশটাই miss করে: *largest* items খুঁজতে একটা *min*-heap লাগে, কারণ একটাই প্রশ্ন matter করে — "তুমি কি আমাদের worst-এর চেয়ে ভালো?"

**Tiny example:** `[5, 1, 9, 3, 7, 6]`-এর 3-টা largest খুঁজে বের করো।

```python
import heapq

def top_k(nums, k):
    club = nums[:k]            # first k get in free
    heapq.heapify(club)        # weakest member at club[0]
    for x in nums[k:]:
        if x > club[0]:        # beats the weakest?
            heapq.heapreplace(club, x)   # pop weakest, push x (one repair)
    return club

print(top_k([5, 1, 9, 3, 7, 6], 3))   # contains 9, 7, 6 in some heap order
```

Dry run: club শুরু হয় `[1, 5, 9]` (weakest = 1)। `3 > 1` → replace, club-এ {3, 5, 9}। `7 > 3` → replace, club-এ {5, 7, 9}। `6 > 5` → replace, club-এ {6, 7, 9}। Cost: O(n log k) time, O(k) memory — এমনকি একটা endless stream-এও কাজ করে।

**Inherits from:** plain heap push/pop; "k most frequent" variant-টা প্রথমে dict দিয়ে count করলে [../05-hashing/](../05-hashing/README.md)-এর frequency counting।

**Representative problems:** [Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/), [Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/), [K Closest Points to Origin](https://leetcode.com/problems/k-closest-points-to-origin/)।

## Pattern 2 — K-way merge

**Trigger words:** "merge k sorted lists", "k sorted arrays/streams", "smallest in a sorted matrix", "smallest range across lists"।

**Core idea:** k-টা sorted list, প্রতিটা list-এ একটা করে cursor। Overall merge-এর পরের item অবশ্যই হতে হবে *কোনো না কোনো cursor যেদিকে দেখাচ্ছে* তার মধ্যে smallest টা। k-টা cursor-value-ই একটা heap-এ রাখো; smallest-টা pop করো, সেই cursor-টা advance করো, তার পরের value push করো।

**Thinking tweak:** ছবিটা ভাবো — **airport security-তে k-টা লাইন আর একজনই officer**। Officer সবসময় সবচেয়ে ছোট number-ওয়ালা front-most লোকটাকে ডাকেন। Heap টা হলো officer-এর চোখে শুধু সামনের k-জন — কখনোই পুরো ভিড় না।

**Tiny example:** merge করো `[1, 4, 7]`, `[2, 5]`, `[3, 6]`।

```python
import heapq

def merge_k(lists):
    h = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(h)                     # (value, which list, index in it)
    out = []
    while h:
        val, li, idx = heapq.heappop(h)
        out.append(val)
        if idx + 1 < len(lists[li]):
            heapq.heappush(h, (lists[li][idx + 1], li, idx + 1))
    return out

print(merge_k([[1, 4, 7], [2, 5], [3, 6]]))   # [1, 2, 3, 4, 5, 6, 7]
```

Heap-এ কখনো k-টার বেশি entry থাকে না: N items-এর জন্য মোট O(N log k), যেখানে "সব ঢেলে দিয়ে sort" হতো O(N log N)। Tuple-এর মাঝের field `i` একই সাথে tie-breaker-এর কাজ করে, যাতে সমান values কখনো lists compare না করে।

**Inherits from:** merge sort-এর two-pointer merge step ([../02-arrays-and-strings/](../02-arrays-and-strings/README.md)) — এটা আসলে "k pointers", যেখানে কোন pointer নড়বে সেটা ঠিক করে একটা heap।

**Representative problems:** [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/), [Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/), [Smallest Range Covering Elements from K Lists](https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/)।

## Pattern 3 — Running median-এর জন্য two heaps

**Trigger words:** "median of a stream", "median of a window", "balance two halves"।

**Core idea:** numbers-গুলোকে একটা lower half আর একটা upper half-এ ভাগ করো। Lower half টা একটা **max-heap**-এ রাখো (এর top = ছোট numbers-দের মধ্যে সবচেয়ে বড়) আর upper half টা একটা **min-heap**-এ (এর top = বড় numbers-দের মধ্যে সবচেয়ে ছোট)। Median থাকে এই দুটো top-এই।

**Thinking tweak:** একটা **seesaw, যার pivot-এ median**। প্রতিটা heap-কে শুধু তার ভেতরের কিনারাটা দেখাতে হয় — মাঝখান ছুঁয়ে থাকা দুটো value। Sizes balanced রাখো (পার্থক্য বড়জোর 1), আর median সবসময় এক peek দূরে।

**Tiny example sketch:**

```text
Stream so far: 5, 2, 8, 1

   lower (max-heap)   |   upper (min-heap)
        [2, 1]        |        [5, 8]
   top = 2  ----------+----------  top = 5
                median = (2 + 5) / 2 = 3.5
```

Insert rule: newcomer-কে `lower`-এর top-এর সাথে compare করে তার side ঠিক করো, তারপর sizes 2-এর ব্যবধানে চলে গেলে একটা top অন্য পাশে সরিয়ে rebalance করো। দুটো step-ই O(log n); median query O(1)। Full code আছে [implementation.py](implementation.py)-তে (`MedianFinder`)।

**Inherits from:** [concept.md](concept.md)-র max-heap-via-negation trick; আর sliding windows-এর ([../02-arrays-and-strings/](../02-arrays-and-strings/README.md)) invariant-ধাঁচের thinking — প্রতিটা step-এর পরে একটা property maintain করা।

**Representative problems:** [Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/), [Sliding Window Median](https://leetcode.com/problems/sliding-window-median/) (lazy deletion যোগ হয়), [IPO](https://leetcode.com/problems/ipo/) (two heaps, কিন্তু অন্য split: affordable vs not-yet-affordable)।

## Pattern 4 — Earliest end দিয়ে scheduling

**Trigger words:** "minimum number of rooms / machines / platforms", "intervals", "can all meetings fit", "CPU picks next job"।

**Core idea:** jobs-গুলোকে start time দিয়ে sort করো। এখন চলমান jobs-দের **end times**-এর একটা min-heap রাখো। নতুন job শুরু হলে, প্রথমে তার start-এর `<=` সব end time pop করে দাও (ওই rooms আবার free)। সবকিছু process করার পরে heap-এর size-ই হলো একসাথে চলা jobs-এর peak সংখ্যা।

**Thinking tweak:** heap টা একটাই প্রশ্নের উত্তর বারবার দেয়: **"এখনকার কোন job সবার আগে শেষ হবে?"** Newcomer-এর জন্য সম্ভাব্য free room ওই একটাই হতে পারে। সব room scan করতে হয় না — earliest end time টাই heap top।

**Tiny example:** meetings `(0, 30), (5, 10), (15, 20)`।

```text
sort by start: (0,30) (5,10) (15,20)

(0,30):  no room ends by 0   -> heap of ends: [30]          rooms = 1
(5,10):  earliest end 30 > 5 -> need new room: [10, 30]     rooms = 2
(15,20): earliest end 10 <= 15 -> reuse it:    [20, 30]     rooms = 2
answer: 2 rooms
```

**Inherits from:** interval sorting; greedy proofs ("earliest end first" হলো classic activity selection-এর সেই একই exchange argument)।

**Representative problems:** [Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/), [Single-Threaded CPU](https://leetcode.com/problems/single-threaded-cpu/), [Car Pooling](https://leetcode.com/problems/car-pooling/) (heap বা difference-array solution)।

## Pattern 5 — Lazy deletion

**Trigger words:** "remove an arbitrary element from the heap", "sliding window with a heap", "values expire / become stale"।

**Core idea:** heap মাঝখান থেকে সস্তায় delete করতে পারে না। তাহলে *কোরো না*। Deletion টা অন্য কোথাও লিখে রাখো (একটা counter dict, বা window bounds-এর সাথে তুলনা), stale entry টা heap-এই থাকতে দাও, আর **stale top-গুলো শুধু তখনই purge করো যখন peek/pop-এর সময় সেগুলো উপরে ভেসে ওঠে।**

**Thinking tweak:** এটা অনেকটা **party-র ভেতর guest-কে তাড়া করার বদলে guest list থেকে নামটা কেটে দেওয়ার মতো**। Bouncer (তোমার pop loop) list-টা তখনই check করে যখন কেউ দরজায় পৌঁছায়।

**Tiny example:** `(-value, index)`-এর max-heap দিয়ে sliding-window maximum:

```python
import heapq

def window_max(nums, k):
    h, out = [], []
    for i, x in enumerate(nums):
        heapq.heappush(h, (-x, i))
        if i >= k - 1:
            while h[0][1] <= i - k:      # top is outside the window?
                heapq.heappop(h)         # purge stale entries lazily
            out.append(-h[0][0])
    return out

print(window_max([1, 3, -1, -3, 5, 3], 3))   # [3, 3, 5, 5]
```

প্রতিটা element একবার push হয় আর বড়জোর একবার pop হয়, তাই পুরো run O(n log n) — যদিও কোনো কোনো window-তে একসাথে কয়েকটা stale top purge হয়। ([../04-stack-and-queue/](../04-stack-and-queue/README.md)-র monotonic deque এটা O(n)-এ করে — heap version টা হলো মনে রাখতে সহজ, general tool।)

**Inherits from:** sliding window-এর size-k discipline; আর heap-এর "শুধু top-টাই দেখা যায়" limitation — যেটাকে এখানে feature বানানো হলো।

**Representative problems:** [Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/) (heap variant), [Sliding Window Median](https://leetcode.com/problems/sliding-window-median/), আর অনেক Codeforces problem যেখানে "multiset with delete" লাগে — দেখো [Codeforces problemset](https://codeforces.com/problemset/)।

## Pattern 6 — Heap + greedy combos

**Trigger words:** "repeatedly combine/smash the two smallest/largest", "always pick the most frequent next", "spend resources on the biggest costs"।

**Core idea:** একটা greedy algorithm একই locally-best choice টা বারবার করে — আর heap হলো সেই machine যেটা "এখনকার best"-টা O(log n)-এ পরিবেশন করে। Greedy ঠিক করে *কী* নেবে; heap সেটা নেওয়াকে fast বানায়।

**Thinking tweak:** দুটো আলাদা প্রশ্ন করো। (1) *Greedy question:* আমি সবসময় পরে কী নেব, আর সেটা কেন safe? (2) *Data-structure question:* ওই pick-টা সস্তায় কোন structure দেয়? যখন (2)-এর উত্তর হয় "একটা changing set-এর min বা max", তখন heap-ই তোমার engine।

**Tiny example:** Last-Stone-Weight ধাঁচের smashing — দুটো heaviest পাথর বারবার smash করো; সমান হলে দুটোই vanish, অসমান হলে পার্থক্যটা থেকে যায়।

```python
import heapq

def last_stone(stones):
    h = [-s for s in stones]       # max-heap via negation
    heapq.heapify(h)
    while len(h) > 1:
        a = -heapq.heappop(h)      # heaviest
        b = -heapq.heappop(h)      # second heaviest
        if a != b:
            heapq.heappush(h, -(a - b))
    return -h[0] if h else 0

print(last_stone([2, 7, 4, 1, 8, 1]))   # 1
```

এই একই skeleton — এক-দুটো extreme pop করো, compute করো, হয়তো কিছু push করে ফেরত দাও — চালায় Huffman coding ("দুটো least frequent merge করো") আর rope-joining cost problems।

**Inherits from:** plain heap operations; greedy reasoning। এই pattern-টাই graphs-এর bridge: **[../09-graphs/shortest-path.md](../09-graphs/shortest-path.md)-এর Dijkstra হলো ঠিক heap + greedy**, যেখানে "এখনকার best" মানে cheapest known path।

**Representative problems:** [Last Stone Weight](https://leetcode.com/problems/last-stone-weight/), [Reorganize String](https://leetcode.com/problems/reorganize-string/), [Furthest Building You Can Reach](https://leetcode.com/problems/furthest-building-you-can-reach/), [Network Delay Time](https://leetcode.com/problems/network-delay-time/) (graph version-টা)।

---

## Pattern picker — এক table-এ

| তুমি শুনছ... | হাত বাড়াও | Heap-এ থাকে |
| --- | --- | --- |
| "k largest / most frequent / closest" | Top-K | size k-এর বর্তমান club (largest-এর জন্য min-heap) |
| "merge k sorted ..." | K-way merge | প্রতি list-এ একটা cursor value |
| "running / window median" | Two heaps | lower half (max-heap) + upper half (min-heap) |
| "minimum rooms / machines" | Earliest end | active jobs-দের end times |
| "delete from a heap / window with heap" | Lazy deletion | live + stale entries; top-এ এলে purge |
| "repeatedly take the extreme and recombine" | Heap + greedy | পুরো evolving multiset টা |

কোনো problem এগুলোর কোনোটার সাথে না মিললেও যদি ফিসফিস করে বলে "best item next" — তাহলে সম্ভবত তোমার heap-ই লাগবে। এই ছয়টা হলো common costume, পুরো wardrobe না।