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

অধ্যায়ের সূচি · অনুশীলন ও সমাধান · মূল ধারণা

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

শেখার ক্রম

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

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

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

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 পড়ুন।

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। একটি অধ্যায়ে সমস্যা থাকলেই তার সেরা সমাধান সেই অধ্যায়ের data structure দিয়ে হবে—এমন ধরে নেবেন না।