Hàng đợi ưu tiên hai đầu (Double-ended Priority Queue) trong C++

Giới thiệu

Hàng đợi ưu tiên hai đầu (Double-ended Priority Queue) cho phép truy xuất và xóa cả phần tử nhỏ nhất và lớn nhất trong O(log n). Chúng ta triển khai bằng std::set của C++ - một cây cân bằng (thường là Red-Black Tree).

Các phép toán hỗ trợ

Mã nguồn hoàn chỉnh

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

struct doubleEndedQueue {
    set<int> s;
    
    int size() {
        return s.size();
    }
    
    string is_empty() {
        return s.size() == 0 ? "True" : "False";
    }
    
    void insert(int x) {
        s.insert(x);
    }
    
    int get_start() {
        return *(s.begin());
    }
    
    int get_end() {
        return *(s.rbegin());
    }
    
    void delete_start() {
        if (s.size() == 0) return;
        s.erase(s.begin());
    }
    
    void delete_end() {
        if (s.size() == 0) return;
        auto end = s.end();
        end--;
        s.erase(end);
    }
};

int main() {
    doubleEndedQueue d;
    
    cout << "is empty: " << d.is_empty() << endl;
    
    d.insert(1);
    d.insert(2);
    d.insert(3);
    d.insert(4);
    d.insert(5);
    
    cout << "is empty: " << d.is_empty() << endl;
    cout << "end (max): " << d.get_end() << endl;
    d.delete_end();
    cout << "end sau khi xóa max: " << d.get_end() << endl;
    
    cout << "start (min): " << d.get_start() << endl;
    d.delete_start();
    cout << "start sau khi xóa min: " << d.get_start() << endl;
    
    return 0;
}

Kết quả chạy chương trình

is empty: True
is empty: False
end: 5
end: 4
start: 1
start: 2

So sánh với các cấu trúc dữ liệu khác

• Priority queue (heap): Chỉ hỗ trợ một đầu (min hoặc max)
• Deque: Hỗ trợ hai đầu nhưng không sắp xếp theo ưu tiên
• Set (BST): Hỗ trợ đầy đủ các phép toán trên với độ phức tạp log n

Ứng dụng thực tế

• Xử lý tác vụ với ưu tiên hai chiều
• Thuật toán tìm đường (A* cần cả min và max)
• Quản lý khoảng thời gian, đoạn thẳng

Kết luận

Triển khai bằng std::set cung cấp giải pháp đơn giản, hiệu quả cho hàng đợi ưu tiên hai đầu với độ phức tạp log n cho mọi phép toán.