Skip to content

Heap Patterns

ছয়টা 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 খুঁজে বের করো।

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/-এর frequency counting।

Representative problems: Kth Largest Element in an Array, Top K Frequent Elements, 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]।

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/) — এটা আসলে "k pointers", যেখানে কোন pointer নড়বে সেটা ঠিক করে একটা heap।

Representative problems: Merge k Sorted Lists, Kth Smallest Element in a Sorted Matrix, 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:

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-তে (MedianFinder)।

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

Representative problems: Find Median from Data Stream, Sliding Window Median (lazy deletion যোগ হয়), 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)।

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, Single-Threaded CPU, 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:

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/-র monotonic deque এটা O(n)-এ করে — heap version টা হলো মনে রাখতে সহজ, general tool।)

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

Representative problems: Sliding Window Maximum (heap variant), Sliding Window Median, আর অনেক Codeforces problem যেখানে "multiset with delete" লাগে — দেখো Codeforces 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, অসমান হলে পার্থক্যটা থেকে যায়।

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-এর Dijkstra হলো ঠিক heap + greedy, যেখানে "এখনকার best" মানে cheapest known path।

Representative problems: Last Stone Weight, Reorganize String, Furthest Building You Can Reach, 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 না।