হিপ ও প্রায়োরিটি কিউ — সবচেয়ে জরুরিটি সবার আগে

১ · সবকিছু সাজানোর দরকার নেই — শুধু “এখন সবচেয়ে জরুরি কে?”

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

লক্ষ করুন, ডাক্তারের সবার একটি সাজানো তালিকা দরকার নেই। কে তৃতীয়, কে সপ্তম — এই মুহূর্তে সে প্রশ্ন অপ্রয়োজনীয়। দরকার শুধু একটি উত্তর: এখন সবচেয়ে জরুরি কে? একজনকে দেখা শেষ হলে আবার একই প্রশ্ন। মাঝে নতুন রোগী আসতেই থাকবেন। এই পর্বের পুরো বিষয়টি দাঁড়িয়ে আছে এই একটি পর্যবেক্ষণের ওপর।

একই প্রশ্ন কম্পিউটারের নানা জায়গায় দেখা যায়:

পর্ব ৩৪-এ (স্ট্যাক ও কিউ) আপনি abstract data type চিনেছেন — আগে ঠিক করা হয় কোন কাজগুলো করা যাবে, ভেতরে কীভাবে হবে তা পরের সিদ্ধান্ত। Priority queue-ও একটি ADT. এর তিনটি মূল কাজ:

সরল সমাধানগুলো কোথায় আটকায়

Heap ছাড়াই কি কাজটি করা যায়? যায়, কিন্তু খরচ বেশি। দুটি সরল পথ ভাবুন:

• এলোমেলো অ্যারে: নতুন রোগী এলে শুধু শেষে বসিয়ে দিন — O(1). কিন্তু সবচেয়ে জরুরিজনকে খুঁজতে প্রতিবার পুরো অ্যারে দেখতে হবে — O(n).
• সবসময় সাজানো অ্যারে: সবচেয়ে জরুরিজন সবসময় শেষে, তাই বের করা O(1). কিন্তু নতুন রোগী ঢোকাতে তাঁর সঠিক জায়গা বের করে পেছনের সবাইকে এক ঘর সরাতে হবে — O(n).

দুটি পথেই কোনো একটি কাজ ধীর। লাখো ঘটনার সিমুলেশনে প্রতিটি কাজে লাখো ধাপ মানে মোট ধাপ লাখ × লাখ। Binary heap একটি মাঝামাঝি পথ নেয়: সে পুরো তালিকা সাজায় না, শুধু “একটু” সাজিয়ে রাখে — ঠিক ততটুকু, যাতে সবচেয়ে বড়টি সবসময় সামনে থাকে। ফলে দুটি কাজই হয় O(log n)-এ। পর্ব ৩৯-এ (Big-O) দেখবেন এই পার্থক্য কত বিশাল।

২ · Binary heap — দুটি নিয়ম মানা একটি ট্রি

পর্ব ৩৫-এ (ট্রি ও BST) আপনি binary tree দেখেছেন — প্রতিটি নোডের সর্বোচ্চ দুটি সন্তান। Binary heap-ও একটি binary tree, তবে সে দুটি নিয়ম মানে।

ক্রমের নিয়মটি খুব দুর্বল — সেটিই এর শক্তি। দুই ভাইবোনের মধ্যে কে বড়, heap তা নিয়ে মাথা ঘামায় না। শুধু বলে, “বাবা-মা সন্তানদের চেয়ে বড়।” একটি অফিসের পদক্রমের কথা ভাবুন। প্রত্যেক বস তাঁর অধীনস্থদের চেয়ে বেশি বেতন পান। তাহলে সবচেয়ে বেশি বেতন কে পান? নিশ্চিতভাবে শীর্ষের এমডি। কিন্তু দুই বিভাগের দুই কর্মীর মধ্যে কার বেতন বেশি, পদক্রম দেখে বলা যায় না। এই “আধা-সাজানো” অবস্থা ধরে রাখা অনেক সস্তা, অথচ আমাদের একমাত্র প্রশ্নের উত্তর দিতে যথেষ্ট।

শেষ দুটি সারি খেয়াল করুন। BST-এর বড় দুশ্চিন্তা ছিল balance — সাজানো ক্রমে মান এলে ট্রি লাঠি হয়ে যায়। Heap-এ সেই ভয় নেই, কারণ আকারের নিয়মই তাকে সবসময় সবচেয়ে চ্যাপ্টা রাখে। ১০ লাখ মানের heap-এর height মাত্র ১৯ — অর্থাৎ ২০টি স্তর।

৩ · অ্যারেতেই ট্রি — pointer ছাড়া

পর্ব ৩৫-এ ট্রির প্রতিটি নোড malloc দিয়ে আলাদা আলাদা তৈরি হয়েছিল, আর নোডগুলো জোড়া ছিল left, right pointer দিয়ে। Heap-এর ক্ষেত্রে এসব কিছুই লাগে না। কারণটি আকারের নিয়মে লুকানো।

Complete tree-এর নোডগুলোকে ওপর থেকে নিচে, প্রতিটি স্তরে বাঁ থেকে ডানে নম্বর দিন — 0, 1, 2, 3… যেহেতু মাঝে কোনো ফাঁক নেই, এই নম্বরগুলো হুবহু একটি অ্যারের ঘরের index হয়ে যায়। পর্ব ১৬-এর (অ্যারে) পাশাপাশি সাজানো ঘরগুলোতেই পুরো ট্রি এঁটে যায়। কে কার সন্তান, তা আর pointer-এ লিখে রাখতে হয় না — একটি সহজ গুণ-ভাগেই বের হয়ে আসে:

এখানে / হলো C-এর পূর্ণসংখ্যা ভাগ — ভাগফলের দশমিক অংশ বাদ যায়, তাই (4 − 1) / 2 = 1 আর (3 − 1) / 2 = 1, দুই ভাইয়েরই parent এক। এমন ট্রিকে বলে implicit tree — ট্রির গঠন ডেটায় লেখা নেই, সূত্রে লেখা। নিচের ডায়াগ্রামে একটি ৭ নোডের max-heap দেখুন, ওপরে ট্রি আর নিচে মেমরির আসল অ্যারে:

৪ · Insert — শেষে বসান, তারপর ওপরে ভাসিয়ে দিন

নতুন মান ঢোকানোর সময় দুটি নিয়মই রক্ষা করতে হবে। আকারের নিয়ম রক্ষা করা সহজ: নতুন মানটি অ্যারের শেষ ঘরে বসান, অর্থাৎ h[n]-এ, তারপর n এক বাড়ান। ট্রিতে এটি শেষ স্তরের প্রথম খালি জায়গা — ট্রি complete-ই থাকল।

কিন্তু ক্রমের নিয়ম ভেঙে যেতে পারে — নতুন মানটি তার parent-এর চেয়ে বড় হতে পারে। তখন দুজনের জায়গা বদল (swap) করুন। মানটি এক স্তর ওপরে উঠল, এবার নতুন parent-এর সাথে তুলনা। যতক্ষণ parent ছোট, ততক্ষণ ওপরে ওঠা — পানিতে বুদবুদ যেমন ভেসে ওঠে। একে বলে sift-up (bubble up). নিচে একটি খালি max-heap-এ ৪০, ৭০, ২০, ৯০, ৫০ — এই ক্রমে পাঁচটি মান ঢোকানো দেখুন:

কেন sift-up কাজ করে? Swap-এর সময় যে parent নিচে নামল, সে আগে থেকেই তার পুরোনো সন্তানদের চেয়ে বড় ছিল (heap property). আর এখন তার জায়গায় যে উঠল, সে আরও বড়। তাই নিচের অংশে কোনো নিয়ম ভাঙে না — সমস্যাটা শুধু ওপরের দিকে সরে যায়, যতক্ষণ না মিটে যায়। প্রতিটি ধাপে একটি তুলনা আর বড়জোর একটি swap, আর ধাপের সংখ্যা height-এর বেশি নয়: মোট খরচ O(log n). দশ লাখ মানের heap-এ বড়জোর ১৯টি swap.

৫ · সবচেয়ে বড়টি বের করা — sift-down

সবচেয়ে বড় মানটি সবসময় h[0]-এ, তাই peek করা O(1) — শুধু একটি ঘর পড়া। কিন্তু সেটি বের করে নিলে (extract-max) root খালি হয়ে যায়। ট্রির মাথা কেটে ফেললে কী হবে?

কৌশলটি চমৎকার: অ্যারের শেষ মানটি তুলে root-এ বসান, আর n এক কমান। এতে আকারের নিয়ম রক্ষা পেল — শেষ স্তরের ডানদিকের নোডটিই শুধু সরল। কিন্তু সেই ছোট মানটি এখন root-এ বসে ক্রমের নিয়ম ভাঙছে। তাই তাকে নিচে নামাতে হবে: দুই সন্তানের মধ্যে বড়টির সাথে তুলনা করুন। সন্তান বড় হলে swap. যতক্ষণ কোনো সন্তান বড়, ততক্ষণ নামা। একে বলে sift-down. আগের heap 90 70 20 40 50 থেকে পরপর দুবার সবচেয়ে বড়টি বের করি:

এবার পুরো ধারণাটি C-তে দেখুন। একটি global অ্যারে h আর তার size n — এই দুটিই পুরো heap. push হলো শেষে বসানো + sift-up, আর pop হলো root নেওয়া + শেষটি ওপরে আনা + sift-down:

#include <stdio.h>
int h[16], n = 0;                          /* heap = array + size */
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }
void push(int x) {                         /* append, then sift-up */
    int i = n++;  h[i] = x;
    for (; i > 0 && h[(i - 1) / 2] < h[i]; i = (i - 1) / 2) swap(&h[i], &h[(i - 1) / 2]);
}
int pop(void) {                            /* root out, last to top, sift-down */
    int top = h[0], i = 0, c;  h[0] = h[--n];
    while ((c = 2 * i + 1) < n) {             /* c = left child */
        if (c + 1 < n && h[c + 1] > h[c]) c++;  /* pick the larger child */
        if (h[c] <= h[i]) break;
        swap(&h[i], &h[c]);  i = c;
    }
    return top;
}
int main(void) {
    push(40); push(70); push(20); push(90); push(50);
    printf("array:");  for (int k = 0; k < n; k++) printf(" %d", h[k]);
    printf("\npeek : %d\n", h[0]);
    while (n > 0) printf("pop  : %d\n", pop());
}

৬ · Heapify আর heapsort — পুরো অ্যারেকে একবারে heap

ধরুন আপনার হাতে আগে থেকেই ১০ লাখ মানের একটি অ্যারে আছে। একটি একটি করে push করলে খরচ O(n log n). কিন্তু আরও চতুর একটি পথ আছে, যার নাম bottom-up heapify: অ্যারেটিকে যেমন আছে তেমনই একটি complete tree ধরুন। প্রতিটি leaf একা একাই একটি heap — তার তো কোনো সন্তান নেই। তাই শেষ যে নোডের সন্তান আছে (index n/2 − 1), সেখান থেকে শুরু করে উল্টো দিকে root পর্যন্ত প্রতিটি নোডে sift-down চালান। নিচ থেকে ওপরে, ছোট ছোট heap জুড়ে বড় heap. [3, 9, 2, 1, 4, 5] দিয়ে দেখি:

Heapsort — heap থেকে সাজানো অ্যারে

Heap থেকে বারবার সবচেয়ে বড়টি বের করলে বড় থেকে ছোট ক্রম আসে — কোডে দেখেছেন। Heapsort এই চিন্তাকে একটি চমৎকার কৌশলে in-place করে: প্রতিবার pop করলে heap এক ঘর ছোট হয়, আর অ্যারের শেষে একটি ঘর খালি হয়। বের করা সবচেয়ে বড় মানটি ঠিক সেই খালি ঘরে রাখুন! প্রথম pop-এর সবচেয়ে বড় মান যায় শেষ ঘরে, দ্বিতীয়টি তার আগের ঘরে… শেষে একই অ্যারে ছোট থেকে বড় সাজানো। কোনো বাড়তি অ্যারে লাগে না।

পর্ব ৪০-এ (সর্টিং) সব sorting পদ্ধতি পাশাপাশি তুলনা করবেন। সেখানে দেখবেন, heapsort প্রায়ই প্রধান খেলোয়াড় নয়, কিন্তু একজন নির্ভরযোগ্য বদলি খেলোয়াড় — introsort quicksort দিয়ে শুরু করে, আর বিপদ দেখলে heapsort-এ চলে যায়।

৭ · Struct-এর priority queue — জরুরি বিভাগের কিউ

বাস্তবে আমরা শুধু সংখ্যা রাখি না। জরুরি বিভাগে প্রতিটি রোগীর নাম আছে, অবস্থার গুরুত্ব (severity) আছে, আর কখন এসেছেন সেই তথ্য আছে। পর্ব ২২-এর struct দিয়ে একজন রোগী বানাই, আর heap-এর তুলনাটি একটি আলাদা ফাংশনে সরিয়ে দিই — before(a, b) সত্য মানে “a-কে b-এর আগে সেবা দিতে হবে”।

একটি প্রশ্ন আগেই ঠিক করতে হবে: দুজনের severity সমান হলে কে আগে? Heap নিজে থেকে এর কোনো নিশ্চয়তা দেয় না — swap-গুলো এমনভাবে হয় যে সমান গুরুত্বের রোগীরা যেকোনো ক্রমে বের হতে পারেন। হাসপাতালে সেটি অন্যায় দেখায়। সমাধানের নাম tie-breaking: প্রত্যেক রোগীকে আসার সময় একটি ক্রমিক টিকিট নম্বর দিন, আর severity সমান হলে ছোট টিকিট আগে।

#include <stdio.h>
typedef struct { const char *name; int sev, arrival; } Patient;
Patient q[16]; int n = 0, ticket = 0;
int before(Patient a, Patient b) { return a.sev != b.sev ? a.sev > b.sev : a.arrival < b.arrival; }
void swap(Patient *a, Patient *b) { Patient t = *a; *a = *b; *b = t; }
void arrive(const char *name, int sev) {
    int i = n++;  q[i] = (Patient){name, sev, ++ticket};
    for (; i > 0 && before(q[i], q[(i - 1) / 2]); i = (i - 1) / 2) swap(&q[i], &q[(i - 1) / 2]);
}
Patient serve(void) {
    Patient top = q[0];  int i = 0, c;  q[0] = q[--n];
    while ((c = 2 * i + 1) < n) {
        if (c + 1 < n && before(q[c + 1], q[c])) c++;
        if (!before(q[c], q[i])) break;
        swap(&q[i], &q[c]);  i = c;
    }
    return top;
}
int main(void) {
    arrive("Rahim", 2); arrive("Karim", 5); arrive("Salma", 3); arrive("Nila", 5); arrive("Joy", 1);
    while (n > 0) { Patient p = serve(); printf("%-5s severity %d  ticket #%d\n", p.name, p.sev, p.arrival); }
}

C-এর standard library-তে কোনো তৈরি priority queue নেই — তাই C প্রোগ্রামাররা heap নিজেরাই লেখেন, আর এজন্যই এটি ইন্টারভিউতে এত জনপ্রিয়। অন্য ভাষায় এটি তৈরি পাওয়া যায়: C++-এর std::priority_queue ডিফল্টভাবে max-heap, Python-এর heapq আর Java-র PriorityQueue min-heap. ভেতরে সবগুলোই এই পর্বের মতো অ্যারে-ভিত্তিক binary heap.

৮ · বাস্তবে heap — Dijkstra থেকে Huffman পর্যন্ত

Heap এমন একটি ডেটা স্ট্রাকচার, যাকে সরাসরি খুব কম দেখা যায়, কিন্তু অসংখ্য বিখ্যাত অ্যালগরিদমের ভেতরে সে ইঞ্জিনের মতো কাজ করে। কয়েকটি দেখি:

৯ · AI-এর যুগে heap কোড — সূত্রে চোখ রাখুন

AI-কে “C-তে একটি priority queue লিখে দাও” বললে কয়েক সেকেন্ডে সুন্দর কোড আসবে। বেশিরভাগ সময় সেটি ঠিকও থাকবে। সমস্যা হলো, heap-এর ভুল সাধারণত crash করে না। প্রোগ্রাম চলে, সংখ্যা ছাপে — শুধু মাঝে মাঝে ভুল ক্রমে। পাঁচটি মান দিয়ে একবার চালিয়ে দেখলে প্রায়ই ধরা পড়ে না। AI-এর heap কোডে যে ভুলগুলো বারবার দেখা যায়:

এসব ভুল ধরার সবচেয়ে শক্তিশালী উপায় শিখবেন পর্ব ৩২-এ (টেস্টিং): একটি ধীর কিন্তু নিশ্চিতভাবে সঠিক সমাধানের সাথে মিলিয়ে দেখা। Heap-এর ক্ষেত্রে সেই নিশ্চিত সমাধান হলো sorting. হাজারটি এলোমেলো মান heap-এ push করুন, তারপর সব pop করুন — ফল হুবহু qsort দিয়ে বড় থেকে ছোট সাজানো অ্যারের সাথে মিলতে হবে। প্রতিটি push ও pop-এর পর পুরো অ্যারেতে heap property যাচাই করুন। একে বলে stress testing, আর একবার লিখে রাখলে AI-এর পরের যেকোনো পরিবর্তনও কয়েক সেকেন্ডে যাচাই হয়ে যায়।

AI-এর heap কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• সূত্রগুলো 0-ভিত্তিক না 1-ভিত্তিক, দেখেছি — আর অ্যারেও সেই একই জায়গা থেকে শুরু হয়েছে
• Sift-down দুই সন্তানের বড়টি (min-heap হলে ছোটটি) বাছে, আর প্রতিটি সন্তানের আগে < n যাচাই আছে
• Pop-এ size ঠিক একবার কমে, আর sift-down চলে কমানোর পরে
• তুলনার চিহ্ন সব জায়গায় এক — একটি before()-এর মতো ফাংশনে রাখা হলে আরও ভালো
• খালি ও ভরা heap, এক মানের heap, আর সব মান সমান — এই অবস্থাগুলোতে চালিয়েছি
• হাজারো এলোমেলো মান দিয়ে ফল sort-এর সাথে মিলিয়েছি, আর Valgrind বা sanitizer-এ কোনো ত্রুটি নেই