Heap, heapsort আর priority queue

১ · Priority queue — হাসপাতালের জরুরি বিভাগের নিয়ম

রাত দুটোয় একটি বড় সরকারি হাসপাতালের জরুরি বিভাগ। সামনে লম্বা ভিড়: কারও জ্বর, কারও হাত কেটেছে, আর এইমাত্র অ্যাম্বুলেন্সে এলেন সড়ক দুর্ঘটনার একজন রোগী, যাঁর রক্তক্ষরণ থামছে না। ডাক্তার কি টিকিটের লাইনের মতো “আগে এলে আগে” নিয়ম মানবেন? না। প্রথমে একজন নার্স প্রত্যেক রোগীকে দেখে ঠিক করেন কার অবস্থা কতটা গুরুতর — একে বলে triage. তারপর ডাক্তার সবসময় ডাকেন সবচেয়ে গুরুতর রোগীকে, তিনি যখনই আসুন না কেন। নতুন রোগী আসছেন, পুরোনোরা চিকিৎসা পেয়ে বেরোচ্ছেন — কিন্তু প্রতিবার প্রশ্ন একটাই: “এখন সবচেয়ে জরুরি কে?”

এই নিয়মে চলা ডেটা স্ট্রাকচারের নাম priority queue (প্রায়োরিটি কিউ). পর্ব ১৪-এর সাধারণ queue মানত FIFO — আগে এলে আগে যায়। Priority queue-তে প্রতিটি উপাদানের সাথে থাকে একটি অগ্রাধিকার (priority বা key), আর বের হয় সবচেয়ে বেশি (অথবা সবচেয়ে কম) অগ্রাধিকারেরটি। এটিও একটি abstract data type (ADT): শুধু কী কাজ করা যায় তা বলে, কীভাবে বানানো হবে তা নয়।

এখন প্রশ্ন, কীভাবে বানাবেন? আগের পর্বগুলোর জিনিস দিয়ে চেষ্টা করি। অসাজানো অ্যারে নিলে insert মানে শেষে বসানো, O(1); কিন্তু সবচেয়ে জরুরিটি খুঁজতে পুরো অ্যারে দেখতে হয়, O(n). সাজানো অ্যারে নিলে উল্টো: সবচেয়ে জরুরিটি এক প্রান্তে, O(1); কিন্তু নতুন রোগীকে সঠিক জায়গায় বসাতে বাকিদের সরাতে হয়, O(n) (insertion sort-এর একটি ধাপের মতো, পর্ব ২০). দুই উপায়েই n টি insert আর n টি extract মিলে O(n²).

Heap-এর কৌশলটি হলো একটি মাঝামাঝি পথ: পুরোপুরি সাজানোর দরকার নেই, শুধু এতটুকু ক্রম রাখতে হবে যাতে সবচেয়ে জরুরিটি সবসময় এক জায়গায় থাকে, আর প্রতিটি পরিবর্তনের পর সেই ক্রম সারাতে log n ধাপের বেশি না লাগে। “পুরো সাজানো” আর “একদম এলোমেলো”-র মাঝখানের এই আংশিক ক্রমই heap-এর শক্তি।

২ · Binary heap — অ্যারেতে লুকোনো একটি tree

পর্ব ২৬-এ tree বিস্তারিত পড়বেন; এখানে যতটুকু লাগে ততটুকুই। একটি binary tree-তে প্রতিটি node-এর সর্বোচ্চ দুটি সন্তান (বাঁ আর ডান)। সবার ওপরের node-কে বলে root, যার কোনো সন্তান নেই তাকে leaf. Root থেকে সবচেয়ে গভীর leaf পর্যন্ত edge-এর সংখ্যাই tree-র উচ্চতা (height).

Heap যে tree ব্যবহার করে, তা একটি বিশেষ ধরনের: complete binary tree. এর প্রতিটি স্তর (level) পুরো ভরা, শুধু শেষ স্তরটি ছাড়া — আর শেষ স্তরটি বাঁ থেকে ডানে ফাঁক ছাড়া ভরা হয়। সিনেমা হলের আসনের কথা ভাবুন: সামনের সারি পুরো না ভরা পর্যন্ত কেউ পেছনের সারিতে বসেন না, আর প্রতিটি সারিতে বসা শুরু হয় বাঁ দিক থেকে। এই নিয়মের দুটি বড় ফল আছে।

• উচ্চতা সবসময় ছোট: n টি node-এর complete binary tree-র উচ্চতা ঠিক ⌊log₂ n⌋. দশ লাখ উপাদানেও উচ্চতা মাত্র ১৯। তাই root থেকে leaf পর্যন্ত যেকোনো যাত্রা O(log n).
• Pointer লাগে না: node-গুলোকে স্তর ধরে বাঁ থেকে ডানে নম্বর দিলে (0, 1, 2, …) সেই ক্রমেই একটি অ্যারেতে রাখা যায়। কোনো ফাঁক নেই, তাই কে কার parent তা শুধু index-এর হিসাব থেকেই বের হয়।

                 a[0]
             /          \
         a[1]            a[2]
        /    \          /    \
     a[3]    a[4]    a[5]    a[6]
     /  \
  a[7]  a[8]          (n = 9: শেষ স্তর বাঁ থেকে ভরা)

অ্যারেতে:  a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
           |__| |_______| |_________________| |_______|
           স্তর 0  স্তর 1        স্তর 2          স্তর 3

যাচাই করুন: উপরের ছবিতে a[4]-এর parent (4 − 1)/2 = 1 — হ্যাঁ, a[1]. a[3]-এর সন্তান 2·3 + 1 = 7 আর 8 — হ্যাঁ, a[7], a[8]. আর n = 9 হলে leaf শুরু index ⌊9/2⌋ = 4 থেকে: a[4] থেকে a[8] — পাঁচটি leaf, অর্থাৎ প্রায় অর্ধেক node-ই leaf. এই তথ্যটি অংশ ৫-এ খুব কাজে লাগবে।

Heap property — একমাত্র নিয়ম

একটি complete binary tree heap হয়, যদি এটি heap property মানে:

• Min-heap: প্রতিটি node-এর মান তার সন্তানদের চেয়ে ছোট বা সমান — a[parent(i)] ≤ a[i]. ফলে সবচেয়ে ছোটটি root-এ, a[0]-এ।
• Max-heap: প্রতিটি node তার সন্তানদের চেয়ে বড় বা সমান. সবচেয়ে বড়টি root-এ।

লক্ষ করুন নিয়মটি কতটা দুর্বল। এটি শুধু parent আর সন্তানের সম্পর্ক বলে; দুই ভাইবোনের (sibling) মধ্যে কে বড়, বা বাঁ subtree-র সবাই ডানের চেয়ে ছোট কি না — কিছুই বলে না। তাই heap সাজানো অ্যারে নয়. [1, 5, 2, 9, 6, 3] একটি বৈধ min-heap, অথচ সাজানো নয়। এই দুর্বলতাই সুবিধা: নিয়ম কম মানে সারাতে কাজও কম। BST-তে (পর্ব ২৭) “বাঁয়ে সব ছোট, ডানে সব বড়” — কঠোর নিয়ম, তাই সেখানে যেকোনো মান খোঁজা যায়; heap-এ যায় না, এখানে শুধু সবচেয়ে ছোট বা সবচেয়ে বড়টি পাওয়া যায়।

৩ · Insert — নতুন উপাদান বুদবুদের মতো ওপরে ওঠে (sift-up)

Min-heap-এ নতুন মান x যোগ করতে হবে। Complete আকৃতি রাখতে x-কে বসানোর জায়গা একটাই — শেষ স্তরের প্রথম খালি ঘর, অর্থাৎ অ্যারের শেষে (index n). আকৃতি ঠিক থাকল, কিন্তু heap property ভাঙতে পারে: x যদি তার parent-এর চেয়ে ছোট হয়। সমাধান: x-কে parent-এর সাথে জায়গা বদল (swap) করুন, আর যতক্ষণ parent বড়, ততক্ষণ চালিয়ে যান। পানির নিচ থেকে বুদবুদ যেমন ওপরে ওঠে — এর নাম sift-up (bubble-up বা swim-ও বলে)। নিচে [2, 4, 3, 7, 9, 5, 8]-এ 1 যোগ করা দেখুন:

কেন এটি ঠিক — invariant. Sift-up চলার পুরো সময় একটি কথা সত্য থাকে: “x যে ঘরে আছে, শুধু সেই ঘর আর তার parent-এর মধ্যে নিয়ম ভাঙা থাকতে পারে; বাকি সব parent–সন্তান জোড়া ঠিক।” শুরুতে এটি সত্য (আগের heap বৈধ ছিল, শুধু x নতুন)। Swap-এর সময় নিচে নামে parent-এর মান p. নিচের ঘরে p-এর নতুন সন্তান হয় x-এর পুরোনো ঘরের সন্তানেরা; p আগে থেকেই তাদের পূর্বপুরুষ ছিল, তাই heap property অনুযায়ী তাদের চেয়ে ছোট বা সমান — নিচের দিকে নিয়ম ঠিক থাকে। আর x ওপরে উঠে p-এর পুরোনো সন্তানের (x-এর ভাইবোনের) চেয়েও ছোট, কারণ x < p ≤ সেই ভাইবোন। ভাঙা জায়গাটি শুধু এক ধাপ ওপরে সরে। লুপ থামে যখন x root-এ পৌঁছায় বা parent ≤ x — তখন কোথাও কোনো ভাঙা নেই। এটি পর্ব ০৩-এর loop invariant পদ্ধতিরই প্রয়োগ।

বিশ্লেষণ: প্রতিটি ধাপে একটি তুলনা আর বড়জোর একটি swap, আর x প্রতি ধাপে এক স্তর ওপরে ওঠে। তাই worst case ⌊log₂ n⌋ ধাপ — সময় O(log n), বাড়তি জায়গা O(1). মজার কথা, এলোমেলো ক্রমে আসা ইনপুটে insert-এর গড় খরচ আসলে ধ্রুবকের কাছাকাছি, কারণ বেশিরভাগ নতুন উপাদান নিচের দিকেই থেকে যায় (অর্ধেক node-ই leaf). Worst case আসে যখন প্রতিটি নতুন মান আগের সবার চেয়ে ছোট — যেমন min-heap-এ কমতে থাকা ক্রমে insert.

৪ · Extract — root সরিয়ে শেষেরটিকে নিচে নামানো (sift-down)

সবচেয়ে ছোট মানটি সবসময় a[0]-এ, তাই peek O(1). কিন্তু সেটি সরিয়ে নিলে root খালি হয়, আর tree-র মাঝখানে একটি গর্ত রাখা যায় না। কৌশল: অ্যারের শেষ উপাদানটি তুলে root-এ বসান, আর অ্যারে এক ঘর ছোট করুন। আকৃতি আবার complete — কিন্তু শেষের উপাদানটি সাধারণত বড় একটি মান, root-এ বসার যোগ্য নয়। এবার উল্টো যাত্রা: তাকে তার ছোট সন্তানের সাথে swap করুন, যতক্ষণ সে কোনো সন্তানের চেয়ে বড়। এর নাম sift-down (bubble-down, sink বা heapify-ও বলে)।

শুদ্ধতা ও খরচ. Invariant এবার আয়নার মতো: “শুধু নামতে থাকা মান আর তার সন্তানদের মধ্যে নিয়ম ভাঙা থাকতে পারে।” ছোট সন্তান c ওপরে উঠলে সে নিজের ভাইবোনের চেয়ে ছোট বা সমান (তাকে বাছাই করাই হয়েছে সেজন্য), আর নিজের পুরোনো subtree-র সবার চেয়েও ছোট বা সমান (heap property) — তাই তার ঘরে নিয়ম ঠিক। ভাঙা জায়গাটি এক স্তর নামে, আর leaf-এ পৌঁছালে বা দুই সন্তানের চেয়েই ছোট বা সমান হলে শেষ। প্রতি স্তরে দুটি তুলনা (দুই সন্তানের মধ্যে, তারপর নিজের সাথে) আর একটি swap, স্তর ⌊log₂ n⌋ টি — তাই extract O(log n), বাড়তি জায়গা O(1).

এবার দুটি কাজ একসাথে কোডে। লক্ষ করুন, sift-down-এ ডান সন্তানের অস্তিত্ব (r < n) আলাদা করে যাচাই করা হয়েছে — শেষ internal node-এর প্রায়ই শুধু বাঁ সন্তান থাকে।

#include <iostream>
#include <utility>
#include <vector>
#include <initializer_list>
using namespace std;
struct MinHeap {
    vector<int> a;
    int push(int x) {                          // append at the end, then sift-up
        a.push_back(x); size_t i = a.size() - 1; int swaps = 0;
        for (; i > 0 && a[(i - 1) / 2] > a[i]; i = (i - 1) / 2, ++swaps) swap(a[(i - 1) / 2], a[i]);
        return swaps;
    }
    pair<int, int> pop() {                     // caller checks !a.empty()
        int top = a[0], swaps = 0;
        a[0] = a.back(); a.pop_back();         // last element jumps to the root
        for (size_t i = 0, n = a.size();; ++swaps) {           // sift-down
            size_t l = 2 * i + 1, r = l + 1, m = i;
            if (l < n && a[l] < a[m]) m = l;
            if (r < n && a[r] < a[m]) m = r;  // m = the smaller child, if smaller than a[i]
            if (m == i) break;
            swap(a[i], a[m]); i = m;
        }
        return {top, swaps};
    }
};
int main() {
    MinHeap h;
    auto show = [&](const char* op, int v, int s) {
        cout << op << v << ": [";
        for (size_t i = 0; i < h.a.size(); ++i) cout << (i ? " " : "") << h.a[i];
        cout << "]  swaps=" << s << '\n';
    };
    for (int x : {4, 2, 3, 7, 9, 5, 8, 1}) show("push ", x, h.push(x));
    while (!h.a.empty()) { auto [v, s] = h.pop(); show("pop  ", v, s); }
}

push 4: [4]  swaps=0
push 2: [2 4]  swaps=1
push 3: [2 4 3]  swaps=0
push 7: [2 4 3 7]  swaps=0
push 9: [2 4 3 7 9]  swaps=0
push 5: [2 4 3 7 9 5]  swaps=0
push 8: [2 4 3 7 9 5 8]  swaps=0
push 1: [1 2 3 4 9 5 8 7]  swaps=3
pop  1: [2 4 3 7 9 5 8]  swaps=2
pop  2: [3 4 5 7 9 8]  swaps=2
pop  3: [4 7 5 8 9]  swaps=2
pop  4: [5 7 9 8]  swaps=1
pop  5: [7 8 9]  swaps=1
pop  7: [8 9]  swaps=1
pop  8: [9]  swaps=0
pop  9: []  swaps=0

class MinHeap:
    def __init__(self):
        self.a = []
    def push(self, x):                    # append at the end, then sift-up
        a, swaps = self.a, 0
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[(i - 1) // 2] > a[i]:
            p = (i - 1) // 2
            a[p], a[i] = a[i], a[p]
            i, swaps = p, swaps + 1
        return swaps
    def pop(self):                        # caller checks the heap is not empty
        a, swaps = self.a, 0
        top = a[0]
        a[0] = a[-1]                      # last element jumps to the root
        a.pop()
        i, n = 0, len(a)
        while True:                       # sift-down
            l, r, m = 2 * i + 1, 2 * i + 2, i
            if l < n and a[l] < a[m]: m = l
            if r < n and a[r] < a[m]: m = r
            if m == i: break
            a[i], a[m] = a[m], a[i]
            i, swaps = m, swaps + 1
        return top, swaps

h = MinHeap()
for x in [4, 2, 3, 7, 9, 5, 8, 1]:
    s = h.push(x)
    print(f"push {x}: [{' '.join(map(str, h.a))}]  swaps={s}")
while h.a:
    v, s = h.pop()
    print(f"pop  {v}: [{' '.join(map(str, h.a))}]  swaps={s}")

push 4: [4]  swaps=0
push 2: [2 4]  swaps=1
push 3: [2 4 3]  swaps=0
push 7: [2 4 3 7]  swaps=0
push 9: [2 4 3 7 9]  swaps=0
push 5: [2 4 3 7 9 5]  swaps=0
push 8: [2 4 3 7 9 5 8]  swaps=0
push 1: [1 2 3 4 9 5 8 7]  swaps=3
pop  1: [2 4 3 7 9 5 8]  swaps=2
pop  2: [3 4 5 7 9 8]  swaps=2
pop  3: [4 7 5 8 9]  swaps=2
pop  4: [5 7 9 8]  swaps=1
pop  5: [7 8 9]  swaps=1
pop  7: [8 9]  swaps=1
pop  8: [9]  swaps=0
pop  9: []  swaps=0

নিজে চালিয়ে দেখুন — heap visualiser

নিচের টুলে “চালিয়ে দেখুন” চাপুন। একটি সংখ্যা লিখে insert চাপলে সেটি শেষে বসে ওপরে উঠবে; extract-min চাপলে root বের হয়ে শেষেরটি নিচে নামবে। যে ঘরগুলোর মধ্য দিয়ে মানটি গেছে, সেগুলো লাল হয়ে জ্বলবে — tree-তে আর নিচের অ্যারেতে একসাথে। ছোট নম্বরগুলো index. লক্ষ করুন, দশটি এলোমেলো মান দিলেও কোনো কাজে swap ৩-এর বেশি হয় না।

const hp = [];                       // the min-heap, drawn as a tree (top) and an array (bottom)
let mark = new Set();
const $ = id => document.getElementById(id);
const cell = i => `<div class="nd${mark.has(i) ? " hl" : ""}">${hp[i]}</div>`;
function draw(msg) {
  let t = "";
  for (let k = 0, s = 0; s < hp.length; k++, s = 2 ** k - 1) {      // one row per level
    t += '<div class="lv">';
    for (let i = s; i < s + 2 ** k; i++) t += `<div class="sl">${i < hp.length ? cell(i) : ""}</div>`;
    t += "</div>";
  }
  $("tr").innerHTML = t; $("msg").textContent = msg;
  $("ar").innerHTML = hp.map((v, i) => `<span class="${mark.has(i) ? "hl" : ""}">${v}<sub>${i}</sub></span>`).join("");
  console.log(msg.padEnd(26) + "[" + hp.join(" ") + "]");
}
function insert(x) {
  hp.push(x); let i = hp.length - 1, sw = 0; mark = new Set([i]);
  while (i > 0 && hp[(i - 1) >> 1] > hp[i]) {                    // sift-up
    const p = (i - 1) >> 1; [hp[p], hp[i]] = [hp[i], hp[p]]; i = p; sw++; mark.add(i);
  }
  draw(`insert(${x}): ${sw} swaps`);
}
function extractMin() {
  if (!hp.length) return draw("heap is empty");
  const m = hp[0], last = hp.pop(); let i = 0, sw = 0; mark = new Set([0]); if (hp.length) hp[0] = last;
  for (;;) {                                                        // sift-down
    const l = 2 * i + 1, r = l + 1; let c = i;
    if (l < hp.length && hp[l] < hp[c]) c = l;
    if (r < hp.length && hp[r] < hp[c]) c = r;
    if (c === i) break;
    [hp[i], hp[c]] = [hp[c], hp[i]]; i = c; sw++; mark.add(i);
  }
  draw(`extractMin() = ${m}: ${sw} swaps`);
}
$("bi").onclick = () => insert(Number($("hv").value)); $("bx").onclick = extractMin;
$("br").onclick = () => { hp.length = 0; for (let k = 0; k < 10; k++) insert(10 + Math.floor(Math.random() * 90)); };
for (const x of [4, 2, 3, 7, 9, 5, 8, 1]) insert(x); extractMin();

insert(4): 0 swaps        [4]
insert(2): 1 swaps        [2 4]
insert(3): 0 swaps        [2 4 3]
insert(7): 0 swaps        [2 4 3 7]
insert(9): 0 swaps        [2 4 3 7 9]
insert(5): 0 swaps        [2 4 3 7 9 5]
insert(8): 0 swaps        [2 4 3 7 9 5 8]
insert(1): 3 swaps        [1 2 3 4 9 5 8 7]
extractMin() = 1: 2 swaps [2 4 3 7 9 5 8]

৫ · Build-heap O(n)-এ — Floyd-এর নিচ থেকে ওপরের কৌশল

ধরুন n টি সংখ্যা আগে থেকেই একটি অ্যারেতে আছে, আর এগুলো দিয়ে heap বানাতে হবে। সরল পথ: একে একে n বার insert. প্রতিটি insert O(log n), মোট O(n log n). আর এটি শুধু ওপরের সীমা নয় — কমতে থাকা ক্রমের ইনপুটে প্রতিটি নতুন উপাদান root পর্যন্ত ওঠে, মোট কাজ log 1 + log 2 + … + log n = Θ(n log n).

১৯৬৪ সালে Robert W. Floyd একটি চমৎকার বিকল্প দেখান, যাকে আজ build-heap বা bottom-up heapify বলে। পর্যবেক্ষণটি সরল: প্রতিটি leaf একা একাই একটি বৈধ heap — তার কোনো সন্তান নেই, নিয়ম ভাঙার সুযোগই নেই। আর অংশ ২-এ দেখেছেন, প্রায় অর্ধেক node-ই leaf. তাই কাজ শুরু করুন শেষ internal node (index ⌊n/2⌋ − 1) থেকে, আর পেছন দিকে root পর্যন্ত প্রতিটি node-এ sift-down চালান। যখন index i-তে sift-down চলে, তখন তার দুই subtree আগেই heap বানানো হয়ে গেছে — তাই i-কে নিচে নামিয়ে সঠিক জায়গায় বসালেই i-এর পুরো subtree heap হয়ে যায়।

Pseudocode — build-heap and heapsort (0-based, MAX-heap, ascending result)

siftDown(a, i, n):                    // heap occupies a[0..n-1]
    while 2i+1 < n:
        c = 2i+1                              // left child
        if c+1 < n and a[c+1] > a[c]: c = c+1     // pick the larger child
        if a[i] >= a[c]: return
        swap a[i], a[c];  i = c

buildHeap(a, n):                      // Floyd 1964: bottom-up
    for i = n/2 - 1 down to 0:  siftDown(a, i, n)

heapsort(a, n):
    buildHeap(a, n)
    for end = n-1 down to 1:
        swap a[0], a[end]                     // current maximum goes to its final place
        siftDown(a, 0, end)                   // the heap shrinks to a[0..end-1]

এখানে max-heap নিয়েছি, কারণ পরের অংশের heapsort ছোট থেকে বড় ক্রমে সাজাতে max-heap ব্যবহার করে। Min-heap-এ শুধু তুলনার চিহ্ন উল্টে যায়। এবার [3, 1, 6, 5, 2, 4] থেকে max-heap বানানো দেখুন:

কেন O(n) — উচ্চতাগুলোর যোগফল

প্রথম দেখায় মনে হয়: n/2 টি node-এ sift-down, প্রতিটি O(log n), তাই O(n log n). এই হিসাব ভুল নয়, কিন্তু ঢিলেঢালা — কারণ বেশিরভাগ node নিচের দিকে, আর নিচের node-এর sift-down ছোট। Node v থেকে sift-down সর্বোচ্চ ততগুলো স্তর নামতে পারে, যতটা v-এর নিজের উচ্চতা h (v থেকে তার নিচের সবচেয়ে গভীর leaf পর্যন্ত দূরত্ব)। এবার গুনুন কোন উচ্চতায় কয়টি node:

• উচ্চতা 0 (leaf): প্রায় n/2 টি — কাজ 0
• উচ্চতা 1: প্রায় n/4 টি — প্রতিটি সর্বোচ্চ 1 swap
• উচ্চতা 2: প্রায় n/8 টি — প্রতিটি সর্বোচ্চ 2 swap
• সাধারণভাবে উচ্চতা h-এ সর্বোচ্চ ⌈n / 2^h+1⌉ টি node, আর root একা উচ্চতা ⌊log₂ n⌋-এ।

তাই মোট swap-এর সংখ্যা সর্বোচ্চ

শেষ ধাপে লেগেছে একটি পরিচিত যোগফল: Σ_h≥0 h/2^h = 1/2 + 2/4 + 3/8 + 4/16 + … = 2. (পর্ব ০৬-এর geometric series Σ x^h = 1/(1 − x)-কে x দিয়ে differentiate করে x দিয়ে গুণ করলে Σ h·x^h = x/(1 − x)²; x = 1/2 বসালে 2.) উচ্চতা h-এর node-এ sift-down সর্বোচ্চ 2h টি তুলনা করে (প্রতি স্তরে দুটি), তাই build-heap-এ তুলনাও 2n-এর বেশি নয় — সময় Θ(n), বাড়তি জায়গা O(1). (⌈⌉ থেকে আসা বাড়তি অংশ যোগ করলেও O(n) বদলায় না।)

একটি নিখুঁত হিসাবও আছে। পুরো ভরা (perfect) binary tree-তে, যার উচ্চতা H আর n = 2^H+1 − 1, সব node-এর উচ্চতার যোগফল ঠিক n − H − 1. যেমন n = 7 (H = 2): root-এর উচ্চতা 2, দুটি node-এর 1, চারটি leaf-এর 0 — যোগফল 4 = 7 − 2 − 1. অর্থাৎ build-heap-এ swap কখনো n-এর সমানও হয় না।

৬ · Heapsort — জায়গায় বসে O(n log n)

কোডের আউটপুটে দেখেছেন, বারবার extract করলে সাজানো ক্রম আসে। কিন্তু বের হওয়া মানগুলো রাখতে আলাদা অ্যারে লাগবে? না — এখানেই heapsort-এর চাতুর্য। Max-heap-এ extract করলে অ্যারের শেষ ঘরটি খালি হয়; আর বের হওয়া সর্বোচ্চ মানটির সাজানো অ্যারেতে ঠিক জায়গা সেই শেষ ঘরই! তাই প্রতিবার a[0]-কে heap-এর শেষ ঘরের সাথে swap করুন, heap-এর আকার এক কমান, আর root থেকে sift-down করুন। অ্যারের বাঁ অংশ heap, ডান অংশ বাড়তে থাকা সাজানো অংশ — একই অ্যারের মধ্যে। ওপরের pseudocode-এর heapsort ঠিক এটিই করে। আগের ডায়াগ্রামের max-heap থেকে শুরু করুন:

বিশ্লেষণ. Build-heap O(n), তারপর n − 1 বার swap আর sift-down, প্রতিটি O(log n) — মোট O(n log n), আর এটি worst case-এও সত্য; quicksort-এর মতো কোনো খারাপ ইনপুটে O(n²)-এ পড়ে না (পর্ব ২২). বেশিরভাগ ইনপুটে আসলে Θ(n log n), কারণ root-এ আনা মানটি অ্যারের শেষ থেকে আসে — সাধারণত ছোট মান — আর প্রায় নিচ পর্যন্ত নামে। Sift-down লুপ দিয়ে লিখলে বাড়তি জায়গা O(1): heapsort একটি in-place অ্যালগরিদম, merge sort-এর (পর্ব ২১) মতো Θ(n) বাড়তি অ্যারে লাগে না।

কিন্তু stable নয়. Stable sort মানে সমান key-এর উপাদানগুলোর আগের ক্রম বজায় থাকে। Heapsort-এ দূরের ঘরের মধ্যে swap হয়, তাই এই ক্রম ভেঙে যায়। ছোট উদাহরণ: [2a, 2b, 1] (দুটি 2, আলাদা চেনার জন্য a আর b). এটি আগেই max-heap. a[0] ↔ a[2]: [1, 2b ¦ 2a]; sift-down: [2b, 1 ¦ 2a]; a[0] ↔ a[1]: [1 ¦ 2b, 2a]. শেষে 2_b চলে গেছে 2_a-এর আগে। রোল নম্বরে আগে থেকে সাজানো ছাত্রদের নম্বর ধরে heapsort করলে একই নম্বরের ছাত্রদের রোল-ক্রম এভাবেই এলোমেলো হয়ে যাবে।

শেষ সারিটি গুরুত্বপূর্ণ। a[i] থেকে a[2i+1]-এ লাফ মানে বড় অ্যারেতে প্রায় প্রতিটি ধাপে মেমরির দূরের অংশ — পর্ব ১০-এর cache-এর সুবিধা হারায়। তাই লাইব্রেরিগুলো heapsort-কে সাধারণত নিরাপত্তা-জাল হিসেবে রাখে: C++-এর std::sort সাধারণত introsort — quicksort দিয়ে শুরু, recursion বেশি গভীর হলে heapsort-এ চলে যায়, যাতে worst case O(n log n) নিশ্চিত থাকে। std::partial_sort (প্রথম k টি সাজানো) সাধারণত heap দিয়েই বানানো হয়।

৭ · লাইব্রেরির heap আর decrease-key

কনটেস্ট আর কাজের কোডে heap নিজে লেখা হয় কমই। তবে দুই ভাষার লাইব্রেরি দুই উল্টো দিক থেকে শুরু করে — এই একটি তথ্য ভুলে অসংখ্য wrong answer হয়।

#include <queue>            // priority_queue
#include <functional>       // greater
priority_queue<int> mx;                               // MAX-heap by default (compare = less)
priority_queue<int, vector<int>, greater<int>> mn;    // MIN-heap
mx.push(5); mx.push(9);
int best = mx.top();                                  // 9 -- read first...
mx.pop();                                             // ...then remove; pop() returns void
// (priority, task id): pairs compare by .first, then .second
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> jobs;
vector<int> v{3, 1, 6, 5, 2, 4};
make_heap(v.begin(), v.end());                        // Floyd's O(n) build-heap, <algorithm>
// push_heap / pop_heap / sort_heap work on a plain vector too

import heapq
h = []                          # heapq works on a plain list: MIN-heap
heapq.heappush(h, 5); heapq.heappush(h, 2)
h[0]                            # 2 -- the smallest, O(1)
heapq.heappop(h)                # removes AND returns 2, O(log n)
data = [3, 1, 6, 5, 2, 4]
heapq.heapify(data)             # O(n) in place, bottom-up

mx = []                         # max-heap trick: store negatives
heapq.heappush(mx, -9); -mx[0]  # 9

tasks = []                      # (priority, counter, task): counter breaks ties
heapq.heappush(tasks, (2, 0, {"name": "backup"}))
heapq.heappush(tasks, (2, 1, {"name": "email"}))
heapq.nlargest(3, data); heapq.nsmallest(3, data)

Decrease-key — কেন অবস্থান মনে রাখতে হয়

জরুরি বিভাগে অপেক্ষার মধ্যেই একজন রোগীর অবস্থা হঠাৎ খারাপ হলো — তাঁর অগ্রাধিকার বাড়াতে হবে। Min-heap-এর ভাষায় এটি decrease-key: ভেতরে থাকা একটি উপাদানের key কমানো। Key কমলে উপাদানটি শুধু ওপরের দিকে নিয়ম ভাঙতে পারে, তাই তার ঘর থেকে sift-up চালালেই হয় — O(log n). কিন্তু আসল প্রশ্ন: উপাদানটি অ্যারের কোন ঘরে আছে? Heap খোঁজার জন্য বানানো নয়; খুঁজতে গেলে O(n).

সমাধান হলো indexed priority queue: একটি বাড়তি অ্যারে pos[id], যা বলে কোন উপাদান heap-এর কোন ঘরে আছে। প্রতিটি swap-এর সাথে pos-ও হালনাগাদ করতে হয়:

// indexed min-heap: heap[] holds item ids, key[id] is the priority, pos[id] = index of id in heap[]
vector<int> heap, pos, key;
void swapNodes(int i, int j) {
    swap(heap[i], heap[j]);
    pos[heap[i]] = i; pos[heap[j]] = j;          // keep the map in sync with EVERY swap
}
void siftUp(int i) {
    for (; i > 0 && key[heap[(i - 1) / 2]] > key[heap[i]]; i = (i - 1) / 2) swapNodes(i, (i - 1) / 2);
}
void decreaseKey(int id, int k) {                // requires k <= key[id]
    key[id] = k;
    siftUp(pos[id]);                             // O(1) to find, O(log n) to repair
}

এর সবচেয়ে বিখ্যাত ব্যবহার Dijkstra-র অ্যালগরিদম (পর্ব ৪৩): প্রতিটি vertex-এর এখন পর্যন্ত জানা দূরত্বই তার key, আর ছোট পথ পাওয়া গেলে key কমে। মুশকিল হলো, std::priority_queue আর heapq — কোনোটিতেই decrease-key নেই। তাই কনটেস্টে প্রচলিত বিকল্প lazy deletion: পুরোনোটি না বদলে নতুন (দূরত্ব, vertex) জোড়া আরেকবার push করুন; পরে কোনো জোড়া pop হলে দেখুন সেটি পুরোনো কি না (d != dist[u] হলে বাদ)। Heap-এ তখন সর্বোচ্চ E টি জোড়া থাকে, প্রতিটি কাজ O(log E) = O(log V) (কারণ E ≤ V²), তাই মোট O((V + E) log V) — indexed heap-এর সমান, কোডে অনেক সহজ, শুধু জায়গা O(V) থেকে বেড়ে O(E). বিস্তারিত পর্ব ৪৩-এ।

৮ · প্রয়োগ — top-k, k টি list জোড়া, running median আর scheduling

সবচেয়ে বড় k টি — উল্টো heap-এর কৌশল

এক কোটি bKash লেনদেনের মধ্যে সবচেয়ে বড় ১০০টি দরকার। সব সাজালে O(n log n), আর সবকিছু মেমরিতে রাখতে হয়। ভালো উপায়টি প্রথমে উল্টো শোনায়: সবচেয়ে বড়গুলোর জন্য রাখুন একটি min-heap, যার আকার সর্বোচ্চ k. প্রতিটি নতুন মান push করুন; আকার k ছাড়ালে pop — অর্থাৎ k + 1 টির মধ্যে সবচেয়ে ছোটটি বাদ। Heap-এর root তখন “এখন পর্যন্ত k-তম বড়” — দরজার দারোয়ানের মতো: এর চেয়ে ছোট কেউ ভেতরে টিকতে পারে না। এটিই top-k সমস্যার মানক সমাধান।

import heapq
def k_largest(nums, k):
    h = []                                 # min-heap of the k largest seen so far
    for x in nums:
        if len(h) < k:
            heapq.heappush(h, x)
        elif x > h[0]:                     # beats the current k-th largest
            heapq.heapreplace(h, x)        # pop the smallest and push x in one O(log k) step
    return sorted(h, reverse=True)         # h[0] alone is the k-th largest

print(k_largest([5, 1, 9, 3, 7, 8, 2], 3))   # [9, 8, 7]

প্রতিটি উপাদানে O(log k) কাজ, তাই সময় O(n log k), জায়গা O(k). k = 100, n = 10⁷ হলে log k ≈ 7, log n ≈ 23 — তিন গুণের বেশি সাশ্রয়, আর মেমরিতে মাত্র ১০০টি মান। ডেটা যদি স্রোতের মতো আসে (stream) আর পুরোটা একসাথে কখনো পাওয়া না যায়, তাহলে এটিই একমাত্র ব্যবহারযোগ্য পথ। পুরো অ্যারে হাতে থাকলে শুধু k-তম মানটির জন্য quickselect গড়ে O(n) (পর্ব ২২). Python-এর heapq.nlargest ভেতরে প্রায় এই কৌশলই ব্যবহার করে।

একই ছাঁচ top-k trending-এ: ফেসবুকে এই ঘণ্টায় কোন ১০টি hashtag সবচেয়ে বেশি এসেছে? প্রথমে একটি hash table-এ প্রতিটি hashtag গুনুন (পর্ব ৩২), তারপর (সংখ্যা, hashtag) জোড়াগুলোর ওপর আকার-১০ min-heap চালান — O(m log 10), যেখানে m আলাদা hashtag-এর সংখ্যা।

k টি সাজানো list জোড়া — k-way merge

পর্ব ২১-এর merge দুটি সাজানো list জোড়ে। k টি হলে? ধরুন দেশের আটটি বিভাগের বোর্ড পরীক্ষার ফল আলাদা আলাদা নম্বর ধরে সাজানো আছে, আর একটি জাতীয় মেধাতালিকা চাই। প্রতিটি list-এর প্রথম উপাদান একটি min-heap-এ রাখুন (মান, কোন list, কোন index). প্রতিবার সবচেয়ে ছোটটি pop করে output-এ দিন, আর সেই list-এর পরের উপাদান push করুন। Heap-এ সবসময় সর্বোচ্চ k টি উপাদান, তাই মোট N টি উপাদানে সময় O(N log k), জায়গা O(k) (output বাদে)। এই k-way merge বড় ডেটা সাজানোর (external sorting) মূল ধাপ — মেমরিতে না ধরা ফাইল টুকরো করে সাজিয়ে তারপর একসাথে জোড়া হয়, আর ডেটাবেস ও search engine-এর index জোড়ায়ও এটি চলে। Python-এ তৈরি আছে: heapq.merge(*lists).

Running median — দুটি heap মুখোমুখি

সংখ্যা একে একে আসছে, আর প্রতিটির পর জানতে হবে এখন পর্যন্ত সবগুলোর median (মাঝের মান) কত। প্রতিবার সাজালে O(n log n) প্রতি ধাপে। কৌশল: সংখ্যাগুলোকে দুই ভাগে রাখুন — ছোট অর্ধেক একটি max-heap low-এ, বড় অর্ধেক একটি min-heap high-এ। দুই heap-এর root দুটি তখন ঠিক মাঝখানে মুখোমুখি দাঁড়িয়ে। নিয়ম দুটি: (১) low-এর সবাই ≤ high-এর সবাই; (২) আকার সমান, অথবা low-এ একটি বেশি। তাহলে মোট বিজোড় হলে median = low-এর root, জোড় হলে দুই root-এর গড়।

#include <cstdio>
#include <functional>
#include <queue>
#include <vector>
#include <initializer_list>
using namespace std;

int main() {
    priority_queue<int> low;                               // max-heap: the smaller half
    priority_queue<int, vector<int>, greater<int>> high;   // min-heap: the larger half
    for (int x : {5, 15, 1, 3, 8, 7, 9}) {
        if (low.empty() || x <= low.top()) low.push(x); else high.push(x);
        if (low.size() > high.size() + 1) { high.push(low.top()); low.pop(); }   // rebalance
        else if (high.size() > low.size()) { low.push(high.top()); high.pop(); }
        double med = low.size() > high.size() ? low.top() : (low.top() + high.top()) / 2.0;
        printf("add %2d: low size %zu, high size %zu, median %.1f\n", x, low.size(), high.size(), med);
    }
}

add  5: low size 1, high size 0, median 5.0
add 15: low size 1, high size 1, median 10.0
add  1: low size 2, high size 1, median 5.0
add  3: low size 2, high size 2, median 4.0
add  8: low size 3, high size 2, median 5.0
add  7: low size 3, high size 3, median 6.0
add  9: low size 4, high size 3, median 7.0

import heapq

low, high = [], []                 # low: max-heap (stored negated), high: min-heap
for x in [5, 15, 1, 3, 8, 7, 9]:
    if not low or x <= -low[0]:
        heapq.heappush(low, -x)
    else:
        heapq.heappush(high, x)
    if len(low) > len(high) + 1:   # keep len(low) == len(high) or len(high) + 1
        heapq.heappush(high, -heapq.heappop(low))
    elif len(high) > len(low):
        heapq.heappush(low, -heapq.heappop(high))
    if len(low) > len(high):
        med = float(-low[0])
    else:
        med = (-low[0] + high[0]) / 2
    print(f"add {x:2d}: low size {len(low)}, high size {len(high)}, median {med:.1f}")

Task scheduling আর simulation

Operating system বা server-এ অনেক কাজ অপেক্ষায় থাকে, প্রতিটির একটি অগ্রাধিকার বা “কখন চালাতে হবে” সময়। পরের কাজটি বাছাই মানেই priority queue. Timer-এর জন্য min-heap প্রচলিত: key = কখন বাজবে; root-এর timer-টিই সবার আগে। যেমন Go ভাষার runtime বহু বছর ধরে timer রাখতে একটি 4-ary heap ব্যবহার করেছে। একই কাঠামো discrete event simulation-এ — ব্যাংকের কাউন্টারে গ্রাহক আসা আর সেবা শেষ হওয়ার ঘটনাগুলো সময় ধরে heap-এ রাখা হয়, আর সিমুলেশন সবসময় সবচেয়ে কাছের ঘটনাটি নেয়। Huffman coding (পর্ব ৫১), Prim-এর MST (পর্ব ৪৫) আর A* search-ও প্রতিটি ধাপে “সবচেয়ে ভালো পরের প্রার্থী” চায় — সবখানেই heap.

৯ · AI-এর যুগে heap — সূত্র ঠিক, index ভুল

“একটি min-heap লিখে দাও” — AI কয়েক সেকেন্ডে লিখবে, আর প্রথম কয়েকটি পরীক্ষায় চলবেও। Heap-এর ভুল সাধারণত লুকিয়ে থাকে এক-অক্ষরের পার্থক্যে: 1-based বইয়ের i/2 সূত্র 0-based অ্যারেতে বসানো, শুধু বাঁ সন্তানের সাথে তুলনা, বা ডান সন্তান আছে কি না যাচাই না করা। ছোট ইনপুটে উত্তর ঠিক আসে, কারণ ভুল শাখা কাজেই লাগে না। আর complexity-র প্রশ্নে AI প্রায়ই build-heap-কে আত্মবিশ্বাসের সাথে O(n log n) বলে, বা heapsort-কে stable বলে দেয়।

Heap-এর কোডে AI সাধারণত যেসব ভুল করে

Heap-এর কোড যাচাইয়ের চেকলিস্ট

• parent/সন্তানের সূত্র আমার index-ব্যবস্থার (0-based না 1-based) সাথে মেলে, index 0-তে হাতে যাচাই করেছি
• প্রতিটি অপারেশনের পর heap property পরীক্ষা করে এমন একটি isHeap() লিখে assert করেছি
• Edge case চালিয়েছি: খালি heap, এক উপাদান, দুই উপাদান, সব সমান, ডুপ্লিকেট, বাড়তে ও কমতে থাকা ইনপুট
• সব উপাদান push করে একে একে pop করলে sorted()-এর সাথে মেলে কি না — হাজারটি এলোমেলো ইনপুটে stress testing করেছি
• top-k বা median-এর উত্তর সাজিয়ে বের করা brute force উত্তরের সাথে মিলিয়েছি
• C++-এ comparator-এর দিক আর Python-এ ঋণাত্মক-কৌশল তিনটি সংখ্যা দিয়ে নিজে দেখে নিয়েছি