C++ Program: Implement Priority Queue

Priority Queue: cấu trúc dữ liệu lấy phần tử có priority cao nhất (hoặc thấp nhất) trước. Không tuân theo FIFO như queue thường.

Đặc điểm

• Phần tử có priority (độ ưu tiên)
• Priority cao hơn → lấy ra trước
• Cùng priority: FIFO
• C++ STL: std::priority_queue (max-heap mặc định)

Triển khai thủ công (Linked list based)

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

struct Node {
    int data;
    int priority;
    Node* next;
};

class PriorityQueue {
    Node* front;
public:
    PriorityQueue() : front(nullptr) {}
    
    void insert(int data, int priority) {
        Node* newNode = new Node{data, priority, nullptr};
        
        // Chèn tại đầu nếu queue rỗng hoặc priority cao hơn front
        if (!front || priority < front->priority) {
            newNode->next = front;
            front = newNode;
        } else {
            // Tìm vị trí chèn: sau các node cùng priority, trước priority thấp hơn
            Node* curr = front;
            while (curr->next && curr->next->priority <= priority) {
                curr = curr->next;
            }
            newNode->next = curr->next;
            curr->next = newNode;
        }
    }
    
    void remove() {
        if (!front) {
            cout << "Queue Underflow\n";
            return;
        }
        Node* temp = front;
        cout << "Deleted: " << temp->data << " (priority: " << temp->priority << ")\n";
        front = front->next;
        delete temp;
    }
    
    void display() const {
        if (!front) {
            cout << "Queue empty\n";
            return;
        }
        cout << "Priority  Data\n";
        for (Node* p = front; p; p = p->next) {
            cout << p->priority << "         " << p->data << '\n';
        }
    }
    
    ~PriorityQueue() {
        while (front) remove();
    }
};

int main() {
    PriorityQueue pq;
    int choice, val, pri;
    
    do {
        cout << "\n1. Insert\n2. Delete\n3. Display\n4. Exit\nChoice: ";
        cin >> choice;
        switch (choice) {
            case 1:
                cout << "Value: "; cin >> val;
                cout << "Priority: "; cin >> pri;
                pq.insert(val, pri);
                break;
            case 2: pq.remove(); break;
            case 3: pq.display(); break;
        }
    } while (choice != 4);
}

C++ STL: std::priority_queue (Khuyến nghị thực tế)

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // greater

int main() {
    // Max-heap (default): phần tử lớn nhất lên đầu
    std::priority_queue maxHeap;
    maxHeap.push(10); maxHeap.push(30); maxHeap.push(20);
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << ' '; // 30 20 10
        maxHeap.pop();
    }
    cout << '\n';
    
    // Min-heap: phần tử nhỏ nhất lên đầu
    std::priority_queue, std::greater> minHeap;
    minHeap.push(10); minHeap.push(30); minHeap.push(20);
    while (!minHeap.empty()) {
        cout << minHeap.top() << ' '; // 10 20 30
        minHeap.pop();
    }
    
    // Custom struct với comparator
    struct Task {
        int id, priority;
        bool operator<(const Task& other) const { 
            return priority < other.priority; // max-heap by priority
        }
    };
    
    std::priority_queue tasks;
    tasks.push({1, 5});
    tasks.push({2, 10});
    tasks.push({3, 3});
    cout << "Top task: " << tasks.top().id << " (pri: " << tasks.top().priority << ")\n";
    
    return 0;
}

Độ phức tạp

Ứng dụng

• Task scheduling (OS, thread pool)
• Dijkstra/A* pathfinding
• Huffman coding
• Event simulation
• K largest/smallest elements