[0]zero-index clytie0x/zero-index

20.5 priority_queue

ห้องฉุกเฉินไม่ได้รักษาตามลำดับที่มาถึง แต่รักษาคนที่อาการหนักที่สุดก่อน คนไข้ใหม่เข้ามาตลอดเวลา และทุกครั้งที่หมอว่างต้องรู้ทันทีว่าใครหนักที่สุดในตอนนั้น งานแบบ "เพิ่มของเข้าไปเรื่อยๆ แล้วหยิบตัวที่มากที่สุดออก" เจอบ่อยมากในโจทย์ เช่น จำลองเหตุการณ์ตามเวลา รวมข้อมูลหลายแถว หรือหาเส้นทางสั้นสุดในบทที่ 28 priority_queue (คิวตามลำดับความสำคัญ) ทำงานนี้อย่างเดียว และทำได้เร็วมาก

หยิบค่ามากสุดก่อน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    priority_queue<int> patients;
    patients.push(3);
    patients.push(9);
    patients.push(5);
    patients.push(9);
    patients.push(1);
    cout << "waiting " << patients.size() << '\n';
    while (!patients.empty()) {
        cout << patients.top() << ' ';
        patients.pop();
    }
    cout << '\n';
    return 0;
}

waiting 5
9 9 5 3 1
  • push(x) ใส่ค่าเข้าไป ค่าซ้ำได้
  • top() ดูค่าที่มากที่สุดโดยไม่เอาออก
  • pop() เอาค่าที่มากที่สุดออก ไม่คืนค่าอะไรกลับมา จึงต้อง top() ก่อนแล้วค่อย pop() เสมอ
  • size() กับ empty() เหมือน container อื่น

ชื่อมีคำว่า queue และใช้ push pop เหมือน queue ในบทที่ 17 แต่ตัวที่ออกไม่ใช่ตัวที่เข้ามาก่อน เป็นตัวที่มากที่สุด สิ่งที่ priority_queue ทำไม่ได้คือ ดูตัวอื่นนอกจากตัวบนสุด วนดูทุกตัว ค้นหาค่า หรือลบค่าที่อยู่ตรงกลาง ถ้าต้องการสิ่งเหล่านี้ให้ใช้ multiset แทน

หยิบค่าน้อยสุดก่อน

ค่าเริ่มต้นคือมากสุดก่อน ถ้าอยากได้น้อยสุดก่อน ต้องบอกสามอย่างในวงเล็บมุม ชนิดของค่า ที่เก็บข้างใน (ใช้ vector เสมอ) และวิธีเปรียบเทียบ greater<int> ซึ่งกลับลำดับให้

#include <bits/stdc++.h>
using namespace std;

int main()
{
    priority_queue<int, vector<int>, greater<int>> lap_times;
    lap_times.push(58);
    lap_times.push(52);
    lap_times.push(61);
    lap_times.push(49);
    while (!lap_times.empty()) {
        cout << lap_times.top() << ' ';
        lap_times.pop();
    }
    cout << '\n';
    return 0;
}

49 52 58 61

อีกวิธีที่เห็นบ่อยในโค้ดของคนอื่นคือใส่ค่าติดลบเข้าไปใน priority_queue ปกติ push(-x) แล้วตอนดึงออกก็กลับเครื่องหมาย -top() ค่าที่น้อยที่สุดจะกลายเป็นค่าติดลบที่มากที่สุด ใช้ได้กับตัวเลข แต่อ่านยากกว่าและลืมกลับเครื่องหมายได้ง่าย เอกสารนี้ใช้ greater

เก็บ pair

บ่อยครั้งที่ต้องเก็บมากกว่าตัวเลขตัวเดียว เช่น ระดับความหนักของอาการคู่กับหมายเลขบัตรคิว priority_queue ของ pair เทียบ first ก่อน ถ้าเท่ากันค่อยเทียบ second เหมือน sort ของ pair ในบทที่ 16 กติกาของห้องฉุกเฉินคือ หนักกว่าได้ก่อน ถ้าหนักเท่ากัน คนที่มาก่อน (บัตรคิวเลขน้อย) ได้ก่อน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    priority_queue<pair<int, int>> waiting;
    int next_ticket = 1;
    for (int i = 0; i < q; i++) {
        char op;
        cin >> op;
        if (op == '+') {
            int level;
            cin >> level;
            waiting.push({level, -next_ticket}); // (1)!
            next_ticket++;
        } else if (waiting.empty()) {
            cout << "nobody\n";
        } else {
            pair<int, int> top = waiting.top();
            waiting.pop();
            cout << "ticket " << -top.second << " level " << top.first << '\n';
        }
    }
    return 0;
}
  1. priority_queue ปกติเอาค่ามากออกก่อนทั้ง first และ second ถ้าเก็บเลขบัตรตรงๆ บัตรเลขมาก (มาทีหลัง) จะได้ก่อน จึงเก็บเป็นค่าติดลบ บัตร 1 กลายเป็น -1 ซึ่งมากกว่า -3 ตอนพิมพ์ค่อยกลับเครื่องหมาย
9
+ 2
+ 5
+ 2
+ 5
-
-
-
-
-

ticket 2 level 5
ticket 4 level 5
ticket 1 level 2
ticket 3 level 2
nobody

บัตร 2 กับ 4 หนักระดับ 5 เท่ากัน บัตร 2 มาก่อนจึงได้ก่อน ตรงนี้คือจุดที่ใช้ค่าติดลบแล้วอ่านง่ายกว่าเขียนวิธีเปรียบเทียบเอง เพราะเงื่อนไขมีทั้งมากก่อนและน้อยก่อนปนกัน

เร็วแค่ไหน

ข้างใน priority_queue คือ heap ต้นไม้ที่ทุกโหนดมากกว่าหรือเท่ากับลูกของมัน ค่ามากสุดจึงอยู่ที่ยอดเสมอ เก็บอยู่ใน vector ธรรมดาโดยไม่ต้องมี pointer เลย push กับ pop แค่สลับของขึ้นลงตามความสูงของต้นไม้ วิธีทำ heap เองทีละขั้นจะได้เรียนในบทที่ 26

คำสั่งเวลา
push(x) pop()O(log N)
top() size() empty()O(1)

multiset ก็หยิบค่ามากสุดได้ด้วย prev(ms.end()) และลบได้ใน O(log N) เท่ากัน แต่ priority_queue เก็บในอาเรย์ติดกัน จึงเร็วกว่าและใช้หน่วยความจำน้อยกว่า ถ้าต้องการแค่ตัวบนสุด ใช้ priority_queue

เทียบกับวิธีตรงไปตรงมา คือเก็บใน vector แล้วไล่หาตัวมากสุดทุกครั้งที่ต้องหยิบ ทดลองใส่ค่าสุ่ม N ค่า แล้วทำซ้ำ N รอบ รอบละหยิบค่ามากสุดออกหนึ่งตัวและใส่ค่าใหม่หนึ่งตัว ของในที่เก็บจึงมี N ตัวตลอด

int best = 0;
for (int j = 1; j < (int)pile.size(); j++) {
    if (pile[j] > pile[best]) {
        best = j;
    }
}
sum_vector += pile[best];
pile[best] = pile.back();
pile.pop_back();
pile.push_back(values[i]);

วัดบนโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 แรม 32 GB ระบบ Windows 11 คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks ตัวเลขเป็นวินาที ช่องแบบ -O2 เป็นค่ากลางของการรันสามครั้ง ช่องแบบ Code::Blocks ที่ N ตั้งแต่ 105 รันครั้งเดียว

Nvector แบบ -O2priority_queue แบบ -O2vector แบบ Code::Blockspriority_queue แบบ Code::Blocks
1040.0340.0010.4040.006
1054.4100.01142.70.064
2 × 10515.70.023178.30.159

vector ต้องไล่ดูของ N ตัวทุกรอบ รวม O(N2) ที่ N สองแสนใช้เวลาเกือบสามนาทีในแบบ Code::Blocks ส่วน priority_queue ใช้ O(log N) ต่อรอบ รวม O(N log N) ไม่ถึงสองในสิบวินาทีทุกแบบ

จำลองเหตุการณ์ตามเวลา

โรงเรียนมีการประชุม N รายการ แต่ละรายการมีเวลาเริ่มและเวลาจบเป็นนาที ประชุมที่เวลาซ้อนกันใช้ห้องเดียวกันไม่ได้ แต่ห้องที่ประชุมจบเวลา 600 พอดี ประชุมถัดไปที่เริ่ม 600 ใช้ต่อได้ ต้องมีห้องประชุมอย่างน้อยกี่ห้อง

คิดแบบเดินตามเวลา เรียงการประชุมตามเวลาเริ่ม แล้วจัดทีละรายการ ทุกครั้งที่มีประชุมจะเริ่ม คำถามเดียวที่สำคัญคือ ในห้องที่มีอยู่ ห้องไหนว่างเร็วที่สุด ถ้าห้องนั้นว่างทันก็ใช้ห้องนั้น ถ้าไม่ทันแปลว่าทุกห้องยังไม่ว่าง ต้องเปิดห้องใหม่ คำถาม "ห้องไหนว่างเร็วที่สุด" คือค่าน้อยสุดของเวลาจบ งานของ priority_queue แบบน้อยสุดก่อนพอดี

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> meetings(n);
    for (int i = 0; i < n; i++) {
        cin >> meetings[i].first >> meetings[i].second;
    }
    sort(meetings.begin(), meetings.end()); // (1)!
    priority_queue<int, vector<int>, greater<int>> ends; // (2)!
    int rooms = 0;
    for (auto meeting : meetings) {
        int start = meeting.first;
        int finish = meeting.second;
        if (!ends.empty() && ends.top() <= start) { // (3)!
            ends.pop();
        } else {
            rooms++;
        }
        ends.push(finish);
    }
    cout << rooms << '\n';
    return 0;
}
  1. pair เรียงตาม first ซึ่งคือเวลาเริ่ม
  2. เก็บเวลาจบของทุกห้องที่เปิดแล้ว ห้องละหนึ่งค่า ตัวบนสุดคือห้องที่ว่างเร็วที่สุด
  3. ห้องที่ว่างเร็วที่สุดว่างทันก่อนประชุมนี้เริ่ม ใช้ห้องนั้นต่อ เอาเวลาจบเก่าออก แล้วใส่เวลาจบใหม่ในบรรทัดที่ 25 ถ้าไม่ทัน เปิดห้องใหม่
6
540 600
600 660
570 630
630 700
545 560
660 720

2

เรียงแล้วได้ 540 545 570 600 630 660 ห้องแรกรับ 540 ถึง 600 ประชุม 545 เริ่มตอนห้องแรกยังไม่ว่างจึงเปิดห้องที่สอง ซึ่งจบ 560 ประชุม 570 ใช้ห้องที่สองต่อ ประชุม 600 ใช้ห้องแรกที่ว่างพอดี ที่เหลือหมุนเวียนอยู่ในสองห้องนี้ ใช้เวลา O(N log N) ทั้งการเรียงและ heap

โจทย์จำลองเหตุการณ์ส่วนใหญ่มีรูปแบบนี้ เก็บ "เหตุการณ์ถัดไปของแต่ละสิ่ง" ไว้ใน heap แล้วหยิบเหตุการณ์ที่เกิดเร็วที่สุดออกมาจัดการทีละอัน แบบฝึกหัดข้อ 9 เป็นร้านซักผ้าที่ต้องใช้ heap สองตัว

รวมรายการที่เรียงแล้ว k รายการ

ร้านสาขา k แห่งส่งยอดขายรายบิลมา แต่ละสาขาเรียงจากน้อยไปมากแล้ว สำนักงานใหญ่อยากได้รายการรวมที่เรียงแล้ว ค่าที่น้อยที่สุดของทั้งหมดต้องเป็นตัวแรกของสาขาใดสาขาหนึ่ง จึงพอที่จะดูแค่ตัวหน้าสุดของทุกสาขา ใส่ตัวหน้าของทุกสาขาลง heap แบบน้อยสุดก่อน หยิบตัวน้อยสุดออกมา แล้วใส่ตัวถัดไปของสาขาเดียวกันเข้าไปแทน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin >> k;
    vector<vector<int>> lists(k);
    for (int i = 0; i < k; i++) {
        int length;
        cin >> length;
        lists[i].resize(length);
        for (int j = 0; j < length; j++) {
            cin >> lists[i][j];
        }
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heads; // (1)!
    vector<int> next_index(k, 0); // (2)!
    for (int i = 0; i < k; i++) {
        if (!lists[i].empty()) {
            heads.push({lists[i][0], i});
            next_index[i] = 1;
        }
    }
    while (!heads.empty()) {
        int value = heads.top().first;
        int list = heads.top().second;
        heads.pop();
        cout << value << ' ';
        if (next_index[list] < (int)lists[list].size()) { // (3)!
            heads.push({lists[list][next_index[list]], list});
            next_index[list]++;
        }
    }
    cout << '\n';
    return 0;
}
  1. เก็บคู่ (ค่า, หมายเลขสาขา) ต้องรู้ว่าค่าที่หยิบออกมาเป็นของสาขาไหน จะได้ใส่ตัวถัดไปของสาขานั้นถูก ชื่อชนิดยาวเพราะต้องเขียน pair<int, int> ซ้ำสามที่
  2. next_index[i] คือตำแหน่งของตัวถัดไปในสาขา i ที่ยังไม่ได้ใส่ลง heap
  3. สาขานี้ยังมีของเหลือ ใส่ตัวถัดไปเข้า heap ถ้าหมดแล้วก็ไม่ใส่ heap จะเล็กลงเรื่อยๆ จนว่าง
3
4 120 250 250 900
3 80 300 310
2 95 1000

80 95 120 250 250 300 310 900 1000

heap มีของไม่เกิน k ตัวตลอดเวลา ถ้ารวมทุกสาขามี T ค่า ใช้เวลา O(T log k) ถ้าเอาทุกค่ามาต่อกันแล้ว sort จะเป็น O(T log T) ซึ่งในทางปฏิบัติก็เร็วพอเมื่อทุกค่าอยู่ในหน่วยความจำได้ วิธี heap ได้เปรียบจริงในสองกรณี คือข้อมูลใหญ่เกินกว่าจะโหลดมาเรียงพร้อมกัน เช่น ไฟล์หลายไฟล์ที่อ่านทีละบรรทัด และกรณีที่ต้องการแค่ M ค่าแรก ซึ่งหยุดหลังหยิบออก M ครั้งได้เลย ใช้เวลาแค่ O(k log k + M log k) ส่วน k log k มาจากการ push ตัวแรกของ k สาขาลง heap ทีละตัวแบบโปรแกรมข้างบน

ค่ามัธยฐานแบบไหลเข้า

แอปวัดเวลาวิ่งรับเวลาของนักวิ่งเข้ามาทีละคน และหลังทุกคนต้องแสดงค่ามัธยฐานของเวลาทั้งหมดที่ได้มาแล้ว ถ้ามีจำนวนคู่ ให้ใช้ตัวกลางตัวที่น้อยกว่า วิธีตรงไปตรงมาคือแทรกเวลาใหม่ลงอาเรย์ที่เรียงไว้แล้วอ่านตัวตรงกลาง แต่การแทรกต้องเลื่อนของครึ่งแถวโดยเฉลี่ย O(N) ต่อครั้ง รวม O(N2)

เคล็ดลับคือแบ่งค่าทั้งหมดเป็นสองกอง กองล่างเก็บครึ่งที่น้อย กองบนเก็บครึ่งที่มาก ค่ามัธยฐานคือค่ามากสุดของกองล่าง กองล่างจึงเป็น heap แบบมากสุดก่อน กองบนเป็น heap แบบน้อยสุดก่อน แล้วรักษาขนาดให้กองล่างมีเท่ากับกองบน หรือมากกว่าหนึ่งตัว

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    priority_queue<int> lower; // (1)!
    priority_queue<int, vector<int>, greater<int>> upper; // (2)!
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (lower.empty() || x <= lower.top()) {
            lower.push(x);
        } else {
            upper.push(x);
        }
        if (lower.size() > upper.size() + 1) { // (3)!
            upper.push(lower.top());
            lower.pop();
        } else if (upper.size() > lower.size()) {
            lower.push(upper.top());
            upper.pop();
        }
        cout << lower.top() << '\n';
    }
    return 0;
}
  1. กองล่าง ครึ่งที่น้อย ตัวบนสุดคือตัวที่มากที่สุดในครึ่งนี้
  2. กองบน ครึ่งที่มาก ตัวบนสุดคือตัวที่น้อยที่สุดในครึ่งนี้ ทุกค่าในกองล่างจึงไม่เกินทุกค่าในกองบน
  3. ใส่ค่าใหม่แล้วขนาดอาจเสียสมดุล ย้ายตัวบนสุดข้ามกองหนึ่งตัวก็กลับมาสมดุล และการย้ายตัวบนสุดไม่ทำให้กฎเรื่องกองล่างไม่เกินกองบนเสีย
7
50 20 80 70 10 90 60

50
20
50
50
50
50
60

หลังค่าที่สี่ ข้อมูลคือ 20 50 70 80 กองล่างมี 20 50 กองบนมี 70 80 ตัวกลางที่น้อยกว่าคือ 50 พอดี ทุกค่าใหม่ทำ push หนึ่งครั้งกับย้ายข้ามกองไม่เกินหนึ่งครั้ง จึงเป็น O(log N) ต่อค่า รวม O(N log N) แทน O(N2)

เทคนิคเก็บค่าเฉพาะส่วนที่สนใจไว้ใน heap ใช้ได้กับคำถามอื่นด้วย เช่น อยากรู้ค่ามากเป็นอันดับที่ K ก็เก็บแค่ K ค่าที่มากที่สุดไว้ใน heap แบบน้อยสุดก่อน ซึ่งเป็นแบบฝึกหัดข้อ 7

เทียบทุกโครงสร้างในบทนี้

โครงสร้างเพิ่ม ลบ ค้นหาค่าน้อยสุด มากสุดค่าแรกที่ ≥ xค่าซ้ำ
setO(log N)O(1)O(log N)ตัดทิ้ง
multisetO(log N)O(1)O(log N)เก็บ
mapO(log N) ตามคีย์O(1) ตามคีย์O(log N) ตามคีย์คีย์ไม่ซ้ำ
unordered_set unordered_mapเฉลี่ย O(1) แย่สุด O(N)ไม่มีไม่มีแบบเดียวกับ set และ map
priority_queueเพิ่มและลบตัวบนสุด O(log N) ค้นหาไม่ได้เฉพาะด้านเดียว O(1)ไม่มีเก็บ

ลองทำให้พัง

แบบที่ 1 ลืมว่าค่าเริ่มต้นคือมากสุดก่อน

อยากได้เวลาวิ่งที่เร็วที่สุด K คน ซึ่งคือเวลาน้อยที่สุด แต่ใช้ priority_queue แบบปกติ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    priority_queue<int> times;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        times.push(t);
    }
    cout << "fastest " << k << ":";
    for (int i = 0; i < k; i++) {
        cout << ' ' << times.top();
        times.pop();
    }
    cout << '\n';
    return 0;
}

6 3
58 52 61 49 55 60

fastest 3: 61 60 58

ได้สามคนที่ช้าที่สุดแทน คำตอบที่ถูกคือ 49 52 55 ต้องประกาศเป็น priority_queue<int, vector<int>, greater<int>> ทุกครั้งที่ใช้ priority_queue ให้ถามตัวเองว่าอยากได้ตัวมากหรือตัวน้อยออกก่อน

แบบที่ 2 เรียก top() ตอนว่าง

#include <bits/stdc++.h>
using namespace std;

int main()
{
    priority_queue<int> patients;
    patients.push(4);
    patients.pop();
    cout << patients.top() << '\n';
    return 0;
}

Code::Blocks คอมไพล์ผ่านโดยไม่มีคำเตือน บนเครื่องที่เขียนเอกสารนี้พิมพ์ 4 ทุกครั้ง ดูเหมือนคนไข้ยังอยู่ ทั้งที่ pop ไปแล้ว เพราะ pop แค่ลดขนาดของ vector ข้างใน ค่าเดิมยังค้างอยู่ในหน่วยความจำ ถ้าคอมไพล์ด้วย -O2 gcc จะเตือน '*<unknown>' is used uninitialized และพิมพ์เลขขยะที่เปลี่ยนไปทุกครั้งที่รัน เช่น -1205706608 การเรียก top() ตอนว่างไม่มี error ให้เห็น ต้องเช็ก empty() ก่อนเองทุกครั้ง

แบบที่ 3 ลืม vector ตรงกลาง

priority_queue<int, greater<int>> lap_times;

laps.cpp:6:36: error: no type named 'value_type' in 'struct std::greater<int>'
    6 |     priority_queue<int, greater<int>> lap_times;
      |                                    ^~
laps.cpp:6:36: error: template argument 3 is invalid
laps.cpp:7:15: error: request for member 'push' in 'lap_times', which is of non-class type 'int'
    7 |     lap_times.push(58);
      |               ^~~~

ช่องที่สองในวงเล็บมุมต้องเป็นที่เก็บ compiler จึงพยายามใช้ greater<int> เป็นที่เก็บแล้วหา value_type ไม่เจอ error ต่อจากนั้นเป็นผลพวง บรรทัดที่ใช้ lap_times ทุกบรรทัดจะขึ้น request for member ซ้ำแบบเดียวกัน แก้ตัวแรกตัวเดียวก็หายหมด ลำดับที่ถูกคือ ชนิด ที่เก็บ วิธีเปรียบเทียบ

สรุป

  • priority_queue<T> ให้ค่ามากสุดที่ top() push กับ pop เป็น O(log N) top เป็น O(1)
  • อยากได้น้อยสุดก่อน ใช้ priority_queue<T, vector<T>, greater<T>>
  • เก็บ pair ได้ เทียบ first ก่อนแล้วค่อย second ใช้ค่าติดลบเมื่อเงื่อนไขของสองค่าต่างทิศกัน
  • เช็ก empty() ก่อน top() และ pop() เสมอ
  • งานจำลองตามเวลา เก็บเหตุการณ์ถัดไปไว้ใน heap แล้วหยิบตัวที่เกิดเร็วที่สุด
  • รวม k รายการที่เรียงแล้วใช้ heap ขนาด k ค่ามัธยฐานแบบไหลเข้าใช้ heap สองกอง

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด