Priority Queue ใน C++ STL

ภาพรวม Priority Queue

Priority Queue เป็น Container Adaptor ที่จัดเรียงองค์ประกอบโดยอัตโนมัติให้องค์ประกอบที่มี "ความสำคัญสูงสุด" (Highest Priority) อยู่ด้านบนสุด ใน C++ ค่าเริ่มต้นคือ Max Heap (ค่ามากที่สุดอยู่บนสุด)

ลักษณะสำคัญ

• ไม่ใช่ FIFO แต่อยู่ที่ Priority-based
• รองรับการเข้าถึงเฉพาะ "Top Element" (ค่าสูงสุด/ต่ำสุด)
• Implementation ใช้ Binary Heap (โดยปกติ)
• Header: <queue>

การประกาศและการใช้งานพื้นฐาน

#include <queue>
#include <vector>
#include <functional>  // สำหรับ greater<>

using namespace std;

// Max Heap (ค่าเริ่มต้น) - ค่ามากที่สุดอยู่บนสุด
priority_queue maxHeap;

// Min Heap - ค่าน้อยที่สุดอยู่บนสุด
priority_queue, greater> minHeap;

// Custom Comparator (เช่น struct/class)
struct CustomCompare {
    bool operator()(const Pair& a, const Pair& b) {
        return a.priority < b.priority;  // Max heap by priority
    }
};
priority_queue, CustomCompare> customPQ;

ฟังก์ชันหลัก (Member Functions)

ตัวอย่างโค้ด C++ สมบูรณ์

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

void printPQ(priority_queue pq) {  // Pass by value เพื่อไม่ทำลายต้นฉบับ
    cout << "PQ contents (top to bottom): ";
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
}

int main() {
    // 1. Max Heap (Default)
    cout << "=== Max Heap (Default) ===" << endl;
    priority_queue maxPQ;
    maxPQ.push(10);
    maxPQ.push(30);
    maxPQ.push(20);
    maxPQ.push(5);
    maxPQ.push(1);
    
    cout << "Size: " << maxPQ.size() << endl;
    cout << "Top: " << maxPQ.top() << endl;
    printPQ(maxPQ);  // 30 20 10 5 1
    
    cout << "\nAfter 2 pops:" << endl;
    maxPQ.pop();  // Remove 30
    maxPQ.pop();  // Remove 20
    printPQ(maxPQ);  // 10 5 1
    
    // 2. Min Heap
    cout << "\n=== Min Heap ===" << endl;
    priority_queue, greater> minPQ;
    minPQ.push(10);
    minPQ.push(30);
    minPQ.push(20);
    minPQ.push(5);
    minPQ.push(1);
    
    cout << "Top (minimum): " << minPQ.top() << endl;  // 1
    printPQ(minPQ);  // 1 5 10 20 30
    
    // 3. Priority Queue with Pair (Custom)
    cout << "\n=== Custom: Task Scheduler ===" << endl;
    struct Task {
        int id;
        int priority;  // มาก = สำคัญกว่า
        string name;
    };
    
    auto cmp = [](const Task& a, const Task& b) {
        return a.priority < b.priority;  // Max heap by priority
    };
    
    priority_queue, decltype(cmp)> taskPQ(cmp);
    taskPQ.push({1, 3, "Low priority"});
    taskPQ.push({2, 10, "High priority"});
    taskPQ.push({3, 5, "Medium priority"});
    taskPQ.push({4, 10, "Also high"});  // Priority เท่ากัน
    
    cout << "Processing tasks by priority:\n";
    while (!taskPQ.empty()) {
        Task t = taskPQ.top(); taskPQ.pop();
        cout << "  Task " << t.id << ": " << t.name << " (priority: " << t.priority << ")" << endl;
    }
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

=== Max Heap (Default) ===
Size: 5
Top: 30
PQ contents (top to bottom): 30 20 10 5 1

After 2 pops:
PQ contents (top to bottom): 10 5 1

=== Min Heap ===
Top (minimum): 1
PQ contents (top to bottom): 1 5 10 20 30

=== Custom: Task Scheduler ===
Processing tasks by priority:
  Task 2: High priority (priority: 10)
  Task 4: Also high (priority: 10)
  Task 3: Medium priority (priority: 5)
  Task 1: Low priority (priority: 3)

การใช้งานขั้นสูง

1. การรวม Priority Queue สองตัว (Merge)

// C++17: ใช้ merge() (ต้องเรียงลำดับก่อน - แต่ PQ เรียงอยู่แล้ว)
// หมายเหตุ: std::priority_queue ไม่มี merge() ต้องย้ายข้อมูลเอง

// วิธีทำ: pop จากอันหนึ่ง push เข้าอีกอัน
while (!pq2.empty()) {
    pq1.push(pq2.top());
    pq2.pop();
}

2. การอัปเดต Priority (Decrease/Increase Key)

STL Priority Queue ไม่รองรับ การอัปเดตค่าในสายกลาง ต้องใช้:

• Lazy Deletion: Push ค่าใหม่ ทิ้งค่าเก่าไว้ ตอน pop ตรวจสอบว่า valid หรือไม่
• ใช้ std::set หรือ std::multiset แทน (รองรับ erase/update)
• ใช้ Boost Heap หรือ Fibonacci Heap

3. การสร้างจาก Range (C++11)

vector vec = {10, 30, 20, 5, 1};
priority_queue pq(vec.begin(), vec.end());  // O(n) heapify

ความซับซ้อนของอัลกอริทึม

ประยุกต์ใช้งานจริง

• Dijkstra's Algorithm - หาเส้นทางสั้นที่สุด
• Huffman Coding - บีบอัดข้อมูล
• Event Simulation - จำลองเหตุการณ์ตามเวลา
• Task Scheduling - OS Process Scheduling
• K-th Largest/Smallest Element - หาค่าที่ k
• A* Pathfinding - AI Game Development

ข้อควรระวัง

• ไม่มี Iterator (ไม่สามารถวนลูปดูค่าทั้งหมดโดยไม่ Pop)
• ไม่รองรับการค้นหา/ลบค่าเฉพาะ (ต้อง Pop จนกว่าจะเจอ)
• Duplicate values ได้ (ไม่เหมือน Set)
• Default เป็น Max Heap ต้องระบุ greater<> สำหรับ Min Heap