POJ 3481 Double Queue：Treap 實現雙端優先隊列（最大/最小優先級服務）

問題描述

銀行服務系統：客戶有 ID (K) 和優先級 (P)。支持操作：

• 1 K P：添加客戶
• 2：服務最高優先級客戶（輸出 ID，刪除）
• 3：服務最低優先級客戶（輸出 ID，刪除）
• 0：結束

K < 10⁶, P < 10⁷。ID 和 P 在當前隊列中唯一。隊列為空時輸出 0。

Treap（樹堆）完美契合

Treap = BST（按優先級 P 排序）+ Heap（按隨機優先級 rnd 維持平衡）。支持：

• 插入 O(log n)
• 刪除最小/最大 O(log n)
• 查找第 k 小（本題不需要）

節點結構

struct Node {
    int ch[2], fa, sz;
    int id, pri;      // 客戶 ID、優先級 P
    int rnd;          // 隨機堆鍵
} t[MAXN];

核心操作

// 旋轉
void rotate(int x, int &k) {
    int y = t[x].fa, z = t[y].fa;
    int d = (t[y].ch[1] == x);
    if (y == k) k = x;
    else t[z].ch[t[z].ch[1]==y] = x;
    t[x].fa = z; t[y].fa = x; t[t[x].ch[d^1]].fa = y;
    t[y].ch[d] = t[x].ch[d^1]; t[x].ch[d^1] = y;
    pushup(y); pushup(x);
}

// Splay（Treap 通常不需要 Splay，但此處代碼混用了 Splay 旋轉邏輯）
// 標準 Treap 插入/刪除用 split/merge 更簡潔

// 插入（按 pri 排序）
void insert(int &k, int id, int pri) {
    if (!k) { k = ++tot; t[k] = {0,0,1,id,pri,rand()}; return; }
    t[k].sz++;
    if (t[k].pri == pri) t[k].w++; // 本題 P 唯一，無需 w
    else if (t[k].pri > pri) { insert(t[k].ch[0], id, pri); if (t[t[k].ch[0]].rnd < t[k].rnd) rotate(t[k].ch[0], k); }
    else { insert(t[k].ch[1], id, pri); if (t[t[k].ch[1]].rnd < t[k].rnd) rotate(t[k].ch[1], k); }
}

// 刪除最小（最左節點）
int delete_min(int &k) {
    if (!t[k].ch[0]) { int id = t[k].id; k = t[k].ch[1]; return id; }
    t[k].sz--;
    return delete_min(t[k].ch[0]);
}

// 刪除最大（最右節點）
int delete_max(int &k) {
    if (!t[k].ch[1]) { int id = t[k].id; k = t[k].ch[0]; return id; }
    t[k].sz--;
    return delete_max(t[k].ch[1]);
}

主邏輯

int main() {
    int op;
    while (read(op), op) {
        if (op == 1) {
            int K = read(), P = read();
            insert(root, K, P);
        } else if (op == 2) { // 最高優先級 = 最大 P
            if (!root) puts("0");
            else printf("%d\n", delete_max(root));
        } else if (op == 3) { // 最低優先級 = 最小 P
            if (!root) puts("0");
            else printf("%d\n", delete_min(root));
        }
    }
}

關鍵點

替代方案：std::set + 兩個迭代器

set> s; // (P, K)
auto it_min = s.begin(), it_max = s.end(); // 需動態維護
// 實際用 set 時：最小 s.begin()，最大 *s.rbegin()
// 刪除後迭代器自動失效，需重新獲取，極其簡潔
// 插入 O(log n)，刪除首/尾 O(1) 攤還

C++ STL set（紅黑樹）代碼量極少，性能完全足夠，工程首選。Treap 適合需額外維護區間信息（如第 k 小、區間翻轉）的場景。

總結

本題是雙端優先隊列的教科書應用。Treap 實現展示了 BST+Heap 結合的平衡樹原理；實際工程中 std::set 或 std::priority_queue（雙堆+延遲刪除）更實用。掌握 Treap 插入/刪除/旋轉邏輯是理解進階平衡樹（Splay、FHQ Treap、主席樹）的基石。