周报

配对堆

2020年3月24日

简介

配对堆是一种可合并堆，支持一下几种操作（假设讨论小根堆）

find_min返回堆中最小元素$O(1)$
merge将两个配对堆合并为 1 个$O(1)$
insert向堆中插入一个元素$O(1)$
decrease_key减小一个元素的值$o(\log n)$[^1]
delete_min删除最小值$O(\log n)$

相比其他可合并堆（左偏树、菲波那契堆），配对堆实现更简单，均摊复杂度优越。

配对堆结构

一个配对堆要么是一个空堆，要么是一个配对树。配对树由一个根元素和可能为空的配对树列表组成。一般选择左孩子右兄弟法存储配对树。

struct Node {
    int v;
    Node *son, *sib;
};

操作

find-min

直接返回堆顶元素。

merge

直接比较两个堆的堆顶元素，将值较大的作为另一个的儿子。

Node* merge(Node *a, Node *b) {
    if (!a) return b;
    if (!b) return a;
    if (a -> v > b -> v) swap(a, b);
    b -> sib = a -> son;
    a -> son = b;
    return a;
}
insert

构造一个只包含需要插入元素的堆，merge 一下。

delete_min

唯一比较复杂的一个操作。

将根的儿子们一对一对地合并，在将合并后的儿子们逐个合并起来。需要注意的是两个过程的方向需要是相反的，这样才能保证操作的复杂度（？？？）。

Node* delete_min(Node *u) {
    return merge_pairs(u -> son);
}
merge_pairs

实现合并一个节点的所有兄弟

Node* merge_pairs(Node *u) {
    if (!u || !u -> sib) return u;
    Node *m = u -> sib, *n = m -> sib;
    return merge(merge(u, m), merge_pairs(m));
}

参考代码

const int MAXN = 100;
struct PairTree {
    int v = 0;
    PairTree *son = 0, *sib = 0;
    PairTree(int x = 0) : v(x) { }
}pool[MAXN], *pptr = pool;
PairTree* newPairTree(int x) {
    pptr -> v = x;
    return pptr++;
}

struct PairHeap {
    PairTree *rt;
    PairHeap() : rt(0) { }

    PairTree* merge(PairHeap &rhs) {
        return rt = merge(rt, rhs.rt);
    }

    PairTree* merge(PairTree *a, PairTree *b) {
        if (!a) return b;
        if (!b) return a;
        if (a -> v > b -> v) swap(a, b);
        b -> sib = a -> son;
        a -> son = b;
        return a;
    }

    PairTree* insert(int x) {
        auto p = newPairTree(x);
        return rt = merge(p, rt);
    }

    void pop() {
        auto bu = rt;
        rt = merge_pairs(rt -> son);
        delete bu;
        return;
    }

    PairTree* merge_pairs(PairTree *u) {
        if (!u || !u -> sib) return u;
        auto m = u -> sib, n = m -> sib;
        return merge(merge(u, m), merge_pairs(n));
    }

    int top() {
        return rt -> v;
    }

    bool empty() {
        return !rt;
    }
};

模板题

luogu P3377【模板】左偏树（可并堆）

Monkey King

[^1]:比较玄学，近似$o(\log n)$

OI-WiKi 配对堆

中文维基

Views: 54

发表评论