配对堆变种
小菜鸟
2020-11-03 21:19:03
# 一个复杂度较为稳定的配对堆变种
## 0x00.前置知识：
* 堆
* 配对堆（**尤其是配对堆的两趟/多趟合并**）
---
## 0x01.简介
我们都知道配对堆是一种思想、实现十分简单，实际运行效率十分优秀的数据结构。
它支持：（以小根堆为例）
* 插入（`insert`）$O(1)$
* 删除最小值（`delete-min`）$O(\log n)$
* 查询最小值（`find-min`）$O(1)$
* 合并（`meld`）$O(1)$
* 减小堆中的关键字（`decrease-key`）$\Omega(\log\log n),\;O(4^{\sqrt{\log\log n}})$
然而我们也知道，由于配对堆的结构过于随意，很多操作均摊复杂度存在较大争议（特别是`meld`和`decrease-key`）
但是考虑到它思想和实现的简洁性，配对堆具有较大的扩展空间。
于是就有了下面要说的这个变种（
---
这个配对堆变种由Amr Elmasry在2009年提出，拥有$O(\log \log n)$的`meld`和`decrease-key`。
论文地址：https://core.ac.uk/download/pdf/204209612.pdf
本文某种程度上是对这篇论文的翻译...
不过说实话我觉得实现难度可能快顶上rank pairing heap了……
并且在数据小的地方实际效率跟朴素配对堆只能持平，合并操作居多时甚至慢于朴素配对堆……
好在思想难度不高，也不需要二项堆作为基础。
---
## 0x02.问题分析
我们先考虑普通配对堆存在的一些问题。
### 1.insert过于粗暴
朴素配对堆直接将新插入结点连到根上的方式会导致势能上升严重。
所以我们考虑给插入结点开一个缓冲区，称为`insert-buffer`。
### 2.decrease-key过于粗暴。
朴素配对堆将整个以被减小结点为根的子树切下来并重新连接。这个做法导致了原本的树形结构被较大地破坏，，，势能也会严重上升，，，
所以我们考虑不切下整棵子树，而是用被切下结点最左边的儿子填补原来的位置。
同时参考插入缓冲区，我们为插入缓冲区以外的所有树开一个缓冲区，称为`pool`。
---
## 0x03.结构及定义
那么我们先考虑一下这种堆的大致结构：
* 一个`insert-buffer`直接存储暂存的结点
* 一个`pool`，存有一组**堆有序**的多叉树
* 一个`minimum-pointer`，用于在这一堆树和结点中维护最值
以下给出我的C++~~伪代码~~
与我的代码并非完全一致，为了可读性隐藏了很多细节
```cpp
template<typename _Tp,typename _Cmp,typename _Alloc>
class elmasry_pairing_heap:private _Cmp
{
public:
struct iterator;
elmasry_pairing_heap();
iterator push(_Tp);
void pop();
const _Tp &top()const;
void modify(const iterator&,_Tp);
void join(elmasry_pairing_heap&);
size_type size()const;
bool empty()const;
private:
struct Node;
struct ptr_cmp;//这个东西将会辅助pool的排序
Node *insert_buffer,*tree_pool,*top_node;
//利用链表来存储insert-buffer和pool
size_type _size;
std::set<Node*> tree_pool_mem;
//为了判断一个结点是否是根，用set存下pool中的所有结点
//过于丑陋，，，会想办法改进的
inline Node *__get_node(_Tp);//分配结点的函数，内部实现可以忽略
inline void __delete_node(Node*);
void __clear();//辅助清空一个堆
void move(elmasry_pairing_heap&);//辅助将一个堆中的所有数据移动到这个堆
void push_to_tree_pool(Node*);//辅助将一个树插入pool
Node *link(Node*,Node*);//直接合并两棵树，返回合并后的根结点
Node *two_pass(Node*);//配对堆的两趟合并
Node *multi_pass(Node*);//配对堆的多趟合并
void combine();
};
```
```cpp
template<typename _Tp,typename _Cmp,typename _Alloc>
struct elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::Node
{
_Tp val;
Node *left,*sibling,*child;
//left:左边的兄弟（如果有）/父亲（如果没有左边的兄弟）
//sibling:右边的兄弟
//child:最左边的儿子
Node(_Tp _val,Node *child_ptr=nullptr):
val(_val),
left(nullptr),
sibling(nullptr),
child(child_ptr)//为了方便识别缓冲区内的结点，初始化时会把child指向该结点自身
{
}
};
```
```cpp
template<typename _Tp,typename _Cmp,typename _Alloc>
struct elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::iterator
{
private:
Node *real_node;
friend class elmasry_pairing_heap;
iterator(Node* ptr):real_node(ptr) {}
public:
iterator():real_node(nullptr){}
const _Tp &operator*()const//普通的解引用，懒得实现->了（
{
return real_node->val;
}
operator void*()const//方便兼容pd_ds的写法，，，实际上比较废（
{
return (void*)real_node;
}
};
```
为了不影响理解，`push_to_pool`也放上来。配对堆本身的相关操作讲解请参考我的另一篇blog。
```cpp
template<typename _Tp,typename _Cmp,typename _Alloc>
void
elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::push_to_tree_pool(Node *ptr)
{
ptr->left=nullptr;
ptr->sibling=tree_pool;
if(tree_pool!=nullptr)tree_pool->left=ptr;
tree_pool=ptr;//链表基操
tree_pool_mem.insert(ptr);
if(top_node==nullptr||_Cmp::operator()(top_node->val,ptr->val))top_node=ptr;//顺手维护
if((1ULL<<tree_pool_mem.size())>_size)combine();//pool过大就combine
}
```
---
显然缓冲区是不能苟到底的。所以我们采用`combine`操作来把所有结点合并成一棵树。
---
## 0x04.核心操作`combine`
对于`insert-buffer`中单个的结点，通过一次多趟合并获得一棵树。
对于`pool`中的树，由于我们不知道每棵树的大小，不一定能找出最优的合并方案...
然而我们可以对`pool`中的树进行一次排序，由此来得出一个接近最优的合并顺序。
把两边出来的树合并后塞`pool`里就成了（
排序十分缓慢...所以我们给出一个限制：`pool`中的树不能超过$\lceil \log n \rceil$棵（$n$是堆中结点个数）
一旦`pool`大小因为其他操作超限，就立即调用一次`combine`。
```cpp
template<typename _Tp,typename _Cmp,typename _Alloc>
void
elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::combine()
{
for(Node *i=insert_buffer;i!=nullptr;i=i->sibling)i->child=nullptr;
insert_buffer=multi_pass(insert_buffer);
typedef std::vector<Node*,node_ptr_alloc_type> table_type;
static table_type root_table;//这里不用管细节。只要知道用vector暂存元素来排序。
root_table.clear();
for(Node *i=tree_pool,*other;i!=nullptr;i=other)
{
other=i->sibling;
i->left=nullptr;
i->sibling=nullptr;
root_table.push_back(i);
}
std::sort(root_table.begin(),root_table.end(),ptr_cmp());
tree_pool=nullptr;
for(typename table_type::const_iterator iter=root_table.begin();iter!=root_table.end();++iter)
{
Node *ptr=*iter;
tree_pool=link(tree_pool,ptr);
}
tree_pool=link(tree_pool,insert_buffer);
insert_buffer=nullptr;
tree_pool_mem.clear();//记得更新pool中的根表
tree_pool_mem.insert(tree_pool);
top_node=tree_pool;//由于很多操作最后可能combine，直接在这维护最值可以省点工作量
}
```
---
## 0x05.具体操作
有了`combine`后就可以轻易写出其他操作了（
---
### insert
因为`insert-buffer`的存在，我们只要直接把新建的结点放入缓冲区就行（
注意同时维护`minimum-pointer`。
```cpp
template<typename _Tp,typename _Cmp,typename _Alloc>
typename
elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::iterator
elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::push(_Tp Value)
{
Node *ptr=__get_node(Value);
if(insert_buffer!=nullptr)insert_buffer->left=ptr;
ptr->sibling=insert_buffer;//链表基操
insert_buffer=ptr;
if(top_node==nullptr||_Cmp::operator()(top_node->val,Value))top_node=ptr;
++_size;
return iterator(ptr);
}
```
---
### delete-min
分类讨论：
* 对于在`pool`里的结点，我们把它的子树两趟合并后重新放回`pool`
* 对于在`insert-pool`里的结点，我们直接删除
但是在删除之后并不能轻易找到新的`minimum-pointer`。所以我们调用一次`combine`，此时合并出的树根就存有最值。
```cpp
template<typename _Tp,typename _Cmp,typename _Alloc>
void
elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::pop()
{
if(top_node->child==top_node)//对于insert-buffer中的结点进行处理
{
if(top_node->left!=nullptr)top_node->left->sibling=top_node->sibling;
if(top_node->sibling!=nullptr)top_node->sibling->left=top_node->left;
if(insert_buffer==top_node)insert_buffer=top_node->sibling;
//链表基操
}
else//对于pool中的结点进行处理
{
Node *son=top_node->child;
if(son!=nullptr)son->left=nullptr;
son=two_pass(son);
if(top_node->left!=nullptr)top_node->left->sibling=top_node->sibling;
if(top_node->sibling!=nullptr)top_node->sibling->left=top_node->left;
if(tree_pool==top_node)tree_pool=top_node->sibling;
if(son!=nullptr)
{
son->sibling=tree_pool;
tree_pool=son;
}
//依然是链表基操
}
--_size;
Node *dead_node=top_node;
combine();
__delete_node(dead_node);
}
```
---
### find-min
略。
```cpp
template<typename _Tp,typename _Cmp,typename _Alloc>
const _Tp&
elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::top()const
{
return top_node->val;
}
```
---
### meld
用类似启发式合并的方法：
* 把较小的堆`combine`后直接存入较大的堆的`pool`。
* 如果较大的堆`pool`超出限制，就`combine`一次。
注意同时维护`minimun-pointer`。
```cpp
template<typename _Tp,typename _Cmp,typename _Alloc>
void
elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::join(elmasry_pairing_heap &other)
{
if(other._size==0)return;
if(_size==0)move(other);//先对二者有空堆的情况特判
if(_size>=other._size)
{
other.combine();
_size+=other._size;
push_to_tree_pool(other.tree_pool);
other.__clear();
}
else
{
combine();
other._size+=_size;
other.push_to_tree_pool(tree_pool);
__clear();
move(other);
}//如上所述
}
```
---
### decrease-key
如果该结点在`insert-buffer`里或者已经是根就直接搞了。
如前文所述，用被减小结点的第一个儿子代替它所在的位置。该结点连同剩下的儿子被作为一棵树放入`pool`。
* 如果`pool`大小超了，就`combine`一次。
依然要注意维护`minimum-pointer`。
```cpp
template<typename _Tp,typename _Cmp,typename _Alloc>
void
elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::modify(const iterator& Iterator,_Tp Value)
{
Node *ptr=(Node*)Iterator.real_node;
if(_Cmp::operator()(top_node->val,Value))top_node=ptr;
ptr->val=Value;
if(ptr->child==ptr||tree_pool_mem.find(ptr)!=tree_pool_mem.end())
{
return;
}
if(ptr->child!=nullptr)//把儿子切出来替换，链表基操
{
Node *replace=ptr->child;
ptr->child=ptr->child->sibling;
if(ptr->child!=nullptr)ptr->child->left=ptr;
if(ptr->left!=nullptr)
{
if(ptr==ptr->left->child)ptr->left->child=replace;
else ptr->left->sibling=replace;
}
if(ptr->sibling!=nullptr)
{
ptr->sibling->left=replace;
}
replace->left=ptr->left;
replace->sibling=ptr->sibling;
}
else//没儿子就直接删，链表基操
{
if(ptr->left!=nullptr)
{
if(ptr==ptr->left->child)ptr->left->child=ptr->sibling;
else ptr->left->sibling=ptr->sibling;
}
if(ptr->sibling!=nullptr)
{
ptr->sibling->left=ptr->left;
}
}
push_to_tree_pool(ptr);
}
```
---
### size&empty
略。
```cpp
template<typename _Tp,typename _Cmp,typename _Alloc>
typename
elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::size_type
elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::size()const
{
return _size;
}
template<typename _Tp,typename _Cmp,typename _Alloc>
bool
elmasry_pairing_heap<_Tp,_Cmp,_Alloc>::empty()const
{
return _size==0;
}
```
---
## 0x06.复杂度分析
咕咕咕。
---
## 0x07.完整的代码实现
直接[广告](https://github.com/OIerTemplate/OIerTemplateLib/blob/master/elmasry_pairing_heap.hpp)
用法参见项目README