0. 什么是配对堆？

配对堆是一种堆型数据结构。它的特点是插入和求极值均是 O(1)O(1)。

它比较冷门，却有着极高的运行效率。

具体可以看看 OI Wiki。

1. 可修改？

一般的配对堆支持 decrease-key（OI Wiki 做法）。可网站上并没有说 increase-key。

这个就是今天主要要讲的。本文将简写“可修改配对堆”为“可改堆”。

2. 可改堆的功能？

名字 英文名（类中名） 复杂度
分离 detach O(1)O(1)
合并 merge
合并子节点 merge_son O(log⁡n)O(\log n)*
弹出节点 pop_node
弹出堆顶 pop
修改 modify
增加节点 push O(1)O(1)
求堆顶 top
*不稳定复杂度。

3. 各种实现

本文以整形小根堆为例。

首先，我们先建一个类。

class Heap
{
public:
    struct HeapNode // 正常的配对堆
    {
        int val;
        HeapNode *fa, *ch, *br;
    } *dts[1000006];
    int len;
    Heap::HeapNode *head;
    Heap()
    {
        head = nullptr;
        len = 0;
    }
};

3.1 分离

这个操作在配对堆中没有，但却是可改堆中的重要一部分。

这个操作就是，将该节点从当前位置分离出来，且将其兄弟节点（如果有）替换到当前位置，而不破坏该节点与其子节点的相对位置。

举个例子：

对于这个以 A 为根的可改堆，我们对 C 进行分离操作，则会变成这样：

实现方式：

根据它的定义，直接写。

Heap::HeapNode *detach(Heap::HeapNode *hp)
    {
        if (hp == head) // 特判堆顶的情形
        {
            head = nullptr;
            return hp;
        }
        if (hp == nullptr) // 特判空指针的情形
        {
            return nullptr;
        }
        Heap::HeapNode **hf = hp->fa == nullptr ? nullptr : hp->fa->ch == hp ? &hp->fa->ch
                                                                             : &hp->fa->br; // 注意判断空指针
        if (hf != nullptr)
        {
            *hf = hp->br;
        }
        if (hp->br != nullptr)
        {
            hp->br->fa = hp->fa;
        }
        hp->fa = nullptr;
        return hp; // 返回分离后的节点
    }

3.2 合并

和配对堆合并基本一样。稍有不同就是合并时要先分离，合并后再加回去。这要求其中至少一个点是一个堆的堆顶。如：

我们要把 C 和 D 合并（假设 C 权值比 D 大），那么合并结果就是：

实现：

Heap::HeapNode *merge(Heap::HeapNode *a, Heap::HeapNode *b) // b 为一个堆的堆顶。
    {
        if (a == nullptr)
        {
            if (head == nullptr)
            {
                head = b;
                return head;
            }
            return nullptr;
        }
        Heap::HeapNode *af = a->fa;
        Heap::HeapNode **ac = af == nullptr ? nullptr : af->br == a ? &af->br
                                                                    : &af->ch; // 先记录相关值
        a = detach(a);
        if (a->val > b->val)
        {
            swap(a, b);
        }
        b->br = a->ch;
        if (a->ch != nullptr)
        {
            a->ch->fa = b;
        }
        a->ch = b;
        b->fa = a;
        if (head == nullptr)
        {
            head = a;
        }
        else if (ac != nullptr)
        {
            *ac = a;
        }
        return a; // 返回合并后的节点
    }

3.3 合并子节点

这和配对堆的合并就不一样了。配对堆是两两配对再合并，而可改堆子节点从后往前一个个合并。这个操作的时间复杂度，“均摊 O(log⁡n)O(\log n)”参考 OI-Wiki。

例如：

我们对 C 进行合并子节点（设 E >> D >> F），则结果为：

Heap::HeapNode *merge_son(Heap::HeapNode *a)
    {
        if (a->ch == nullptr)
        {
            return nullptr;
        }
        if (a->ch->br == nullptr)
        {
            return detach(a->ch);
        }
        Heap::HeapNode *end = a->ch;
        while (end->br != nullptr) // 枚举到最后
        {
            end = end->br;
        }
        end = end->fa;
        Heap::HeapNode *msr = detach(end->br);
        while (end != a)
        {
            Heap::HeapNode *_tmp = end;
            end = end->fa;
            detach(_tmp);
            msr = merge(msr, _tmp);
        }
        return msr; // 子节点合并之后的堆顶
    }

3.4 弹出节点

这个也是可改堆与配对堆的重要不同点之一。

这个操作是：先将儿子合并（保证子树没有兄弟），然后（空则换成该节点的兄弟）替换到当前位置，将该节点断绝关系。

例如：

我们将 D 弹出（设 G >> H），则结果为：

或将 E 弹出，则结果为：

实现：还是根据定义直接写。

Heap::HeapNode *pop_node(Heap::HeapNode *a)
    {
        Heap::HeapNode *msr = merge_son(a);
        if (msr == nullptr) // 注意一堆（不是数据结构）特判
        {
            return detach(a);
        }
        if (a == head)
        {
            head = msr;
            a->ch = nullptr;
            return a;
        }
        msr->fa = a->fa;
        msr->br = a->br;
        Heap::HeapNode **ac = a->fa == nullptr ? nullptr : a->fa->br == a ? &a->fa->br
                                                                          : &a->fa->ch;
        if (ac != nullptr)
        {
            *ac = msr;
        }
        a->br->fa = msr;
        a->fa = a->ch = a->br = nullptr;
        return a; // 弹出的节点
    }

3.5 弹出堆顶

吾已有弹出节点，弹出堆顶岂不易乎？

Heap::HeapNode *pop()
    {
        return pop_node(head);
    }

3.6 修改

是不是这时候感觉没那么神秘了？

分三步：弹出，修改值，合并。

Heap::HeapNode *modify(Heap::HeapNode *a, int val)
    {
        a = pop_node(a);
        a->val = val;
        merge(head, a);
        return a;
    }

3.7 增加节点

这是个可加可不加的封装函数。其过程就是根据值建一个节点然后合并。

Heap::HeapNode *push(int a)
    {
        if (head == nullptr)
        {
            head = dts[len++] = (Heap::HeapNode *)malloc(sizeof(Heap::HeapNode));
            head->br = head->fa = head->ch = nullptr;
            head->val = a;
            return head;
        }
        else
        {
            Heap::HeapNode *_tmp = dts[len++] = (Heap::HeapNode *)malloc(sizeof(Heap::HeapNode));
            _tmp->br = _tmp->fa = _tmp->ch = nullptr;
            _tmp->val = a;
            merge(head, _tmp);
            return _tmp; // 返回建的节点的指针
        }
    }

3.8 求最值

根据可改堆的定义，堆顶即所求。

int top()
    {
        return head == nullptr ? 0 : head->val;
    }

至此，可改堆的所有功能都写完了！

完整版的代码：

class Heap
{
public:
    struct HeapNode
    {
        int val;
        HeapNode *fa, *ch, *br;
    } *dts[1000006];
    int len;
    Heap::HeapNode *head;
    Heap()
    {
        head = nullptr;
        len = 0;
    }
    Heap::HeapNode *detach(Heap::HeapNode *hp)
    {
        if (hp == head)
        {
            head = nullptr;
            return hp;
        }
        if (hp == nullptr)
        {
            return nullptr;
        }
        Heap::HeapNode **hf = hp->fa == nullptr ? nullptr : hp->fa->ch == hp ? &hp->fa->ch
                                                                             : &hp->fa->br;
        if (hf != nullptr)
        {
            *hf = hp->br;
        }
        if (hp->br != nullptr)
        {
            hp->br->fa = hp->fa;
        }
        hp->fa = nullptr;
        return hp;
    }
    Heap::HeapNode *merge(Heap::HeapNode *a, Heap::HeapNode *b)
    {
        if (a == nullptr)
        {
            if (head == nullptr)
            {
                head = b;
                return head;
            }
            return nullptr;
        }
        Heap::HeapNode *af = a->fa;
        Heap::HeapNode **ac = af == nullptr ? nullptr : af->br == a ? &af->br
                                                                    : &af->ch;
        a = detach(a);
        if (a->val > b->val)
        {
            swap(a, b);
        }
        b->br = a->ch;
        if (a->ch != nullptr)
        {
            a->ch->fa = b;
        }
        a->ch = b;
        b->fa = a;
        if (head == nullptr)
        {
            head = a;
        }
        else if (ac != nullptr)
        {
            *ac = a;
        }
        return a;
    }
    Heap::HeapNode *merge_son(Heap::HeapNode *a)
    {
        if (a->ch == nullptr)
        {
            return nullptr;
        }
        if (a->ch->br == nullptr)
        {
            return detach(a->ch);
        }
        Heap::HeapNode *end = a->ch;
        while (end->br != nullptr)
        {
            end = end->br;
        }
        end = end->fa;
        Heap::HeapNode *msr = detach(end->br);
        while (end != a)
        {
            Heap::HeapNode *_tmp = end;
            end = end->fa;
            detach(_tmp);
            msr = merge(msr, _tmp);
        }
        return msr;
    }
    Heap::HeapNode *pop_node(Heap::HeapNode *a)
    {
        Heap::HeapNode *msr = merge_son(a);
        if (msr == nullptr)
        {
            return detach(a);
        }
        if (a == head)
        {
            head = msr;
            a->ch = nullptr;
            return a;
        }
        msr->fa = a->fa;
        msr->br = a->br;
        Heap::HeapNode **ac = a->fa == nullptr ? nullptr : a->fa->br == a ? &a->fa->br
                                                                          : &a->fa->ch;
        if (ac != nullptr)
        {
            *ac = msr;
        }
        a->br->fa = msr;
        a->fa = a->ch = a->br = nullptr;
        return a;
    }
    Heap::HeapNode *pop()
    {
        return pop_node(head);
    }
    Heap::HeapNode *modify(Heap::HeapNode *a, int val)
    {
        a = pop_node(a);
        a->val = val;
        merge(head, a);
        return a;
    }
    Heap::HeapNode *push(int a)
    {
        if (head == nullptr)
        {
            head = dts[len++] = (Heap::HeapNode *)malloc(sizeof(Heap::HeapNode));
            head->br = head->fa = head->ch = nullptr;
            head->val = a;
            return head;
        }
        else
        {
            Heap::HeapNode *_tmp = dts[len++] = (Heap::HeapNode *)malloc(sizeof(Heap::HeapNode));
            _tmp->br = _tmp->fa = _tmp->ch = nullptr;
            _tmp->val = a;
            merge(head, _tmp);
            return _tmp;
        }
    }
    int top()
    {
        return head == nullptr ? 0 : head->val;
    }
};

4. 应用

4.1 【模版】堆

板子题，而且不需要修改操作。

// Luogu P3378 https://www.luogu.com.cn/problem/P3378
#include <iostream>
#include <cstdlib>
using namespace std;

class Heap
{}; // 省略 Heap 代码。内容和以上一样。

int main()
{
    Heap hp;
    int n;
    cin >> n;
    while (n--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x;
            cin >> x;
            hp.push(x);
        }
        else if (op == 2)
        {
            cout << hp.top() << endl;
        }
        else if (op == 3)
        {
            hp.pop();
        }
    }
    return 0;
}

4.2 zj

可以用可改堆来代替 priority_queue（这样不会 TLE ，当然会 pbds 也行）。因为某些原因，这里代码只写了使用部分，关于题目实现未贴上去。

#include <iostream>
using namespace std;
inline long long read()
{
}

#include <iostream>
// 复制的，反正重复 include 不会报错
#include <cstdlib>
using namespace std; // 重复 using 也一样

class Heap
{}; // 省略 Heap 代码。内容和以上一样。除了 dts 数组开到 7000006。

long long as;
long long a[10000007];
Heap::HeapNode *m[10000007];
Heap mt;
long long sm;

int main()
{
    for (int i = 1; i <= n; i++)
    {
        m[i] = mt.add(mi);
    }
    while (q--)
    {
        int op = read(), i, x;
        if (op == 1)
        {
        }
        else if (op == 2)
        {
            mt.modify(m[i], x);
        }
        else if (op == 3)
        {
            long long mm = mt.min();
        }
    }
    return 0;
}
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2021104657号
  3. Worker 0, 10ms
  4. Powered by Hydro v4.14.1 Community