priority_queue: আগে বেরোয় সবচেয়ে বড়টা, যখনই আসুক না কেন

Maria স্কুলের computer lab-এর help desk চালায়, আর ওখানে প্রতিটা report পায় একটা urgency, মানে কতটা জরুরি তার একটা নম্বর। ও সবসময় খোলা report-গুলোর মধ্যে সবচেয়ে জরুরিটা আগে নেয়, সেটা যখনই আসুক। Module 6-এর queue হলে পরীক্ষার ঠিক আগে নষ্ট হওয়া projector-টাকে চল্লিশটা password reset-এর পেছনে দাঁড়িয়ে থাকতে হতো। Vector হলে প্রতিবার নেওয়ার আগে পুরোটা খুঁজতে হতো, নয়তো sort করতে হতো। এই lesson ওকে এমন একটা container দেবে, যেটা সবচেয়ে বড়টা আগে ফেরত দেয়, আর দেখাবে কেন কাজটা সস্তা।

আগে কে বেরোয়: সবচেয়ে বড়টা

Module 6-এর lesson 04 প্রতিটা কাজকে একটাই প্রশ্ন করেছিল: আগে কে বেরোবে? Stack-এর উত্তর সবচেয়ে নতুনটা, queue-এর সবচেয়ে পুরোনোটা। Maria-র দরকার তৃতীয় উত্তরটা, সবচেয়ে জরুরিটা, আর এর container হলো priority_queue: ভেতরে যা আছে, তার মধ্যে সবচেয়ে বড় মানটা ও সবসময় আগে ফেরত দেয়। নিচে একই চারটা urgency দুটোতেই ঢোকে।

Queue urgency-গুলো ফেরত দেয় ঠিক যে ক্রমে এসেছিল। আর priority_queue আগে দেয় 9, যদিও ওটা এসেছিল দ্বিতীয়। তাই priority_queue-এ আসার ক্রম কিছুই ঠিক করে না; ঠিক করে শুধু মানগুলো।

Heap: একটা tree, যে একটাই কথা দেয়

একের পর এক push-এর মাঝেও সবচেয়ে বড়টা চট করে খুঁজে পেতে priority_queue ওর মানগুলো রাখে একটা heap-এ, যেটা এক রকমের tree। প্রতিটা মান বসে একটা node-এ, আর একটা node-এর নিচে বড়জোর দুইটা node ঝুলতে পারে, ওরা ওর child। কোনো child-এর ঠিক উপরের node-টা ওর parent, আর একদম উপরের যে node-এর কোনো parent নেই, সেটা root।

Heap কথা দেয় একটাই: প্রতিটা parent ওর child-দের চেয়ে ছোট না। তাই উপরের দিকে উঠতে থাকলে মান কখনো কমে না, আর root-এ থাকে সবার চেয়ে বড়টা। এর বাইরে আর কোনো কথা নেই: একই parent-এর দুই child যেকোনো ক্রমে থাকতে পারে। তাই সবচেয়ে বড়টা সবসময় root-এ অপেক্ষা করে, আর বাকিরা থাকে আধা-সাজানো।

Tree-টা থাকে একটা vector-এর ভেতরে

Tree-টা আলাদা আলাদা node দিয়ে বানানো হয় না। ওটা লেখা হয় একটাই vector-এ, level ধরে ধরে, বাঁ থেকে ডানে। Level মানে tree-র একটা সারি, আর slot মানে vector-এর একটা ঘর, গোনা শুরু 0 থেকে। ছবিতে আছে সেই heap, যেটা পরের অংশ বানাবে।

প্রতিটা level-এ জায়গা থাকে উপরেরটার দ্বিগুণ: 1, 2, 4, 8, এভাবে বাড়তে থাকে। তাই 7টা মান ভরায় 3টা level, আর 1,000,000 মানের জন্য লাগে মাত্র 20টা। এই সংখ্যাটা মোটামুটি log₂ n, মানে n-কে কতবার অর্ধেক করলে 1-এ পৌঁছাও। কোন slot কার parent, সেই হিসাব করবে lesson 05। তাই একটা মান বড়জোর মোটামুটি log₂ n level পার হয়, আর এজন্যই heap দ্রুত থাকে।

Push মানে উপরে ওঠা

এবার heap-টাকে নড়তে দেখো। একটা খালি priority_queue<int>-এ ছয়টা মান ঢোকে: 4, 9, 2, 7, 5 আর 8। ধাপে ধাপে চালাও, আর খেয়াল করো প্রতিটা নতুন মান কোথায় গিয়ে বসে, আর কতদূর ওঠে।

প্রতিটা push একই দুইটা কাজ করেছে। নতুন মান গেছে পরের খালি slot-এ, একদম নিচের level-এ। তারপর ও উপরে উঠেছে: যতক্ষণ parent-এর চেয়ে বড়, ততক্ষণ parent-এর সাথে swap করেছে; এমন প্রতিটা swap-কে বলে sift up। 9 উঠে গেছে root পর্যন্ত, 7 আর 8 এক level করে, আর 2 আর 5 একটুও ওঠেনি। তাই একটা push প্রতি level-এ বড়জোর একটা swap করে।

Pop মানে নিচে নামা

Pop root-টা সরিয়ে দেয়, আর heap-কে ফাঁকটা ভরাতে হয় ওর কথা না ভেঙে। ছয়টা push যে heap বানাল, তার উপর দুইটা pop দেখো।

প্রতিটা pop শেষ মানটাকে slot 0-এ এনেছে, কারণ vector ওর শেষ slot-টা সস্তায় ছেড়ে দিতে পারে। তারপর মানটা নেমেছে: বড় child-টা যতক্ষণ ওর চেয়ে বড়, ততক্ষণ দুজন swap করেছে, আর এই ধাপের নাম sift down। বড় child-টাই উপরে ওঠে, তাই heap-এর কথা রক্ষা হয়। তাই push-এর মতো pop-ও একটা মানকে বড়জোর মোটামুটি log₂ n level পার করায়।

প্রতিটা পুরো push বা pop-এর পরে widget দুটো দেখায় ঠিক সেই vector, যেটা Compiler Explorer-এ GCC 12-এর priority_queue-এর ভেতরে ছিল। Pop-এর ভেতরে library একটা shortcut নেয়, যেটা একই vector-এ গিয়ে পৌঁছায়; সেটা দেখাবে lesson 05। তাই এই ছবিগুলো আসল layout-ই দেখায়।

প্রথম দিনেই যে syntax লাগবে

#include <queue>

priority_queue<T> pq;      an empty priority_queue of T
pq.push(x);                add x; it climbs to its place
pq.top()                   the largest element; it stays in
pq.pop();                  remove the largest; returns nothing
pq.size()    pq.empty()    how many, and whether there are none

#include <functional>     for greater
#include <vector>
priority_queue<T, vector<T>, greater<T>> small;
                           the smallest on top instead

তাই priority_queue-এর কাজের call তিনটা, stack-এর মতোই push, top আর pop, আর top() সবসময় দেখায় সবচেয়ে বড়টা।

push, top আর pop

push(x) x-কে heap-এ ঢোকায়। top() বলে এই মুহূর্তে ভেতরের সবচেয়ে বড় মান কোনটা, আর pop() সেটা সরিয়ে দেয়। এই program প্রতিটা বদলের পরে top আর size print করে।

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(4);
    pq.push(9);
    pq.push(2);
    cout << "top " << pq.top() << ", size " << pq.size() << '\n';
    pq.pop();
    cout << "top " << pq.top() << ", size " << pq.size() << '\n';
    pq.push(7);
    cout << "top " << pq.top() << ", size " << pq.size() << '\n';
    return 0;
}

top 9, size 3
top 4, size 2
top 7, size 3

Pop-এর পরে top হলো 4, কারণ বাকিদের মধ্যে ওটাই সবচেয়ে বড়। তারপর 7 এল, আর পুরোনো 4-কে টপকে সোজা top-এ চলে গেল। তাই top() সবসময় জবাব দেয় ভেতরে থাকা সবচেয়ে বড় মানটা দিয়ে, সেটা যখনই আসুক।

pop কিছুই ফেরত দেয় না: আগে পড়ো, তারপর pop

Bob এক লাইনেই সবচেয়ে বড় মানটা নিতে আর সরাতে চায়, তাই ও লেখে এটা।

priority_queue<int> pq;
pq.push(4);
int x = pq.pop();

Runner-এর flag-এ GCC 12 থেমে যায় error: void value not ignored as it ought to be দিয়ে। void মানে "কোনো মান না": pop() top-টা সরায়, কিন্তু হাতে কিছুই ফেরত দেয় না, ঠিক Module 6-এর stack-এর pop()-এর মতো। সমাধান দুই লাইনের: আগে একটা read, তারপর একটা pop।

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(4);
    pq.push(9);
    pq.push(2);
    int x = pq.top();
    pq.pop();
    cout << "took " << x << ", now the top is " << pq.top() << '\n';
    return 0;
}

took 9, now the top is 4

তাই Module 6-এর জোড়াটাই থাকছে: আগে top() দিয়ে দেখো, তারপর pop()।

সবচেয়ে ছোটটা আগে, এক লাইনে

কিছু কাজে আগে লাগে সবচেয়ে ছোটটা: সবচেয়ে সস্তা ভাড়া, সবচেয়ে কম অপেক্ষা। তখন priority_queue-এর angle bracket-এ আরও দুইটা জিনিস দাও: ভেতরে যে vector রাখবে সেটা, আর greater<int>, যেটা ক্রম উল্টে দেয়। দুটোই বুঝিয়ে বলবে lesson 02; আপাতত লাইনটা হুবহু লেখো।

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : {4, 9, 2, 7, 5, 8}) {
        pq.push(x);
    }
    cout << "smallest first:";
    while (!pq.empty()) {
        cout << ' ' << pq.top();
        pq.pop();
    }
    cout << '\n';
    return 0;
}

smallest first: 2 4 5 7 8 9

while (!pq.empty()) loop-টা top পড়ে, print করে, pop করে, যতক্ষণ না কিছুই বাকি থাকে; এমন loop-কে বলে drain। তাই একটু লম্বা একটা declaration দিলেই heap সবচেয়ে বড়টার বদলে সবচেয়ে ছোটটা আগে দেয়, আর প্রতিটা call একই থাকে।

খালি priority_queue: Zara-র প্রথম test

Zara সবসময় খালি case আগে চালায়। ও একটা খালি priority_queue-কে ওর top জিজ্ঞেস করে।

priority_queue<int> pq;
cout << "top: " << pq.top() << '\n';

Runner-এর flag-এ এটা কোনো বার্তা ছাড়াই compile হয়েছে। Compiler Explorer-এর GCC 12.2-এ একবার চালাতে program কিছুই print করেনি, crash করেছে SIGSEGV দিয়ে, যে signal আসে নিজের না এমন memory পড়তে গেলে। এমনকি top: -ও আসেনি, কারণ ওটা তখনো cout-এর কাছে ধরা ছিল। তারপর ও একটা খালি priority_queue pop করে।

priority_queue<int> pq;
pq.pop();
cout << "size after pop: " << pq.size() << '\n';

সেবার print হয়েছে size after pop: 18446744073709551615, আর program স্বাভাবিকভাবেই শেষ হয়েছে। Pop ভেতরের vector-এর শেষটাকে ওর শুরুরও নিচে নামিয়ে দিয়েছে, তাই size ঘুরে গিয়ে হয়ে গেছে ওর পক্ষে সম্ভব সবচেয়ে বড় সংখ্যা। এরপর একটা push(7) আর একটা top() SIGSEGV দিয়ে crash করেছে। দুটোই undefined behaviour: কী হবে, C++ standard কিছুই বলে না। তাই যে top() বা pop()-এর input তোমার হাতে নেই, তার আগে প্রতিবার if (!pq.empty()) লেখো।

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    while (!pq.empty()) {
        cout << "pop " << pq.top() << '\n';
        pq.pop();
    }
    return 0;
}

pop 8
pop 5
pop 1

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> scores;
    for (int s : {120, 340, 90, 410, 275}) {
        scores.push(s);
        cout << "pushed " << s << ", best so far " << scores.top() << '\n';
    }
    scores.pop();
    cout << "the best player leaves; next best " << scores.top() << '\n';
    return 0;
}

pushed 120, best so far 120
pushed 340, best so far 340
pushed 90, best so far 340
pushed 410, best so far 410
pushed 275, best so far 410
the best player leaves; next best 340

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    priority_queue<string> words;
    words.push("pear");
    words.push("apple");
    words.push("fig");
    words.push("banana");
    cout << "largest first:";
    while (!words.empty()) {
        cout << ' ' << words.top();
        words.pop();
    }
    cout << '\n';
    return 0;
}

largest first: pear fig banana apple

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int> marks;
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        marks.push(m);
    }
    int place = 1;
    while (!marks.empty()) {
        cout << place << ". " << marks.top() << '\n';
        marks.pop();
        place++;
    }
    return 0;
}

1. 92
2. 92
3. 88
4. 81
5. 75
6. 67
7. 59

#include <iostream>
using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(5);
    cout << pq.top() << '\n';
    return 0;
}

priority_queue<int> pq;
pq.push(5);
cout << pq.front() << '\n';

priority_queue<int> fares;
fares.push(30);
fares.push(12);
fares.push(45);
cout << "cheapest fare first:";
while (!fares.empty()) {
    cout << ' ' << fares.top();
    fares.pop();
}
cout << '\n';

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    priority_queue<int> reports;
    for (int i = 0; i < n; i++) {
        string op;
        cin >> op;
        if (op == "add") {
            int urgency = 0;
            cin >> urgency;
            // Add the new report's urgency to reports.
        } else {
            // op is "take": print the highest urgency and remove it,
            // or print none if no report is open.
        }
    }

    // Print the urgencies still open, from the highest to the lowest,
    // separated by single spaces, or the word empty if none is left.

    return 0;
}

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    priority_queue<int> tallest;
    priority_queue<int, vector<int>, greater<int>> shortest;
    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;
        // Push h into both heaps.
    }

    // Print n heights on one line, separated by single spaces: the tallest,
    // then the shortest, then the next tallest, and so on. Every student
    // stands in the row exactly once, so print exactly n heights.

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> heap;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        heap.push_back(x);
        // x is now in the last slot. While it is larger than the value in
        // its parent's slot, swap the two and move up to the parent's slot.
        // Then print heap, slot 0 first, separated by single spaces.
    }
    return 0;
}

এরপর lesson 02 priority_queue-এর প্রতিটা operation একটা একটা করে দেখাবে, প্রতিটার খরচসহ, আর ওর ক্রম বেছে নেওয়ার সব উপায়।