Heap / Priority Queue — Concept¶

একটাই 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-টার জন্য:

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

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

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 দেখো।

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/)।
Random access-এ index অনুযায়ী k-th smallest দরকার — sorted list বা selection algorithm বেশি মানানসই।
প্রায়ই arbitrary middle elements delete করতে হবে — heap-এ তখন lazy-deletion trick লাগে (দেখো 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¶

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¶

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¶

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) হিসেবে¶

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