Rank-Pairing Heap(赋级配对堆)学习笔记

Rank-Pairing Heap(rp-heap，赋级配对堆)是一种堆。（废话

复杂度和Fib堆相同(如果不知道Fib堆什么复杂度，百度，请)。

论文里说rp堆更优秀(理由是维护的信息更少)，但wiki说Fib堆更快一些。

不过至少我觉得rp-heap要好写得多(论文里好像也这么说了)。~~毕竟我这种菜鸡都能写出来~~

这里是论文和课件，都是嘤文的。(Tarjan大毒瘤)

还有EtaoinWu的《配对堆与赋级配对堆（Rank Pairing Heaps）》。本文的大部分中文译名参考自此。

先膜为敬，EtaoinWu Orz

本文中采用中文还是英文名似乎很混乱。

写blog不易，给个赞吧（

以下默认是最小堆(小根堆)。

前置知识 : 二叉树，渐进记号，摊还分析，初中一年级数学（废话

不必要的前置知识 : 配对堆，二项堆，Fib堆

说几句闲话，学习Fib堆可以参考洛咕谷日爆报 :

#214[木木！]安塔的二项堆&斐波那契堆学习笔记

但是个人认为这篇文章讲得不够详细(就连势函数都是不完整的)，如果想详细了解，还是推荐算法导论，或者这篇blog。

想要代码的话，LOJ的最短路板子按代码长度排序，第一页有两个Fib堆实现，分别是lcomyn的373378和qiyue7的187001。在上面那篇日报评论区和那个blog里也有。~~看出来Fib堆难写了~~

0.一些记号

H

表示一个rp-heap，

x,y

表示结点或数值，

key

表示关键字。

\operatorname{left}

和

\operatorname{right}

分别表示左儿子和右儿子。

\operatorname{insert}(x,H)=\operatorname{merge}(\operatorname{make-heap}(x),H)

\operatorname{delete}(p,H)=\operatorname{decrease-key}(p,-\inf,H),\operatorname{extract-min}(H)

文中提到"其它操作复杂度"时，不包括以上两操作的复杂度。

1.半树(half tree)

1.1.定义

rp-heap是由若干半树(

\text{half tree}

)组成的。

\text{half-ordered}

的定义是 : 每个结点的

key

比左子树任意结点的

key

小。

半树的定义是 : 根节点没有右儿子，且所有点满足

\text{half-ordered}

性质的二叉树。（请仔细读这句话

由此可以立刻得出根是树中最小的。

1.2. $\operatorname{link}$

\operatorname{link}

是半树的基本操作，用于把两棵半树合并成一棵半树。它的过程如下 :

\operatorname{link}

接受两棵半树的根

x,y

作为输入。不妨假设

x

的

key

更小。把

x

的左儿子拿下来，接到

y

的右儿子上，然后把

y

接到

x

的左儿子上。这是

O(1)

的。

这是从论文里拿的图 :

显然合并后仍然满足半树定义。

1.3. $\operatorname{rank}$ (级)

定义

\operatorname{rank}:V \to \mathbb{N}

。单个节点的

\operatorname{rank}

是

0

。定义一棵半树的

\operatorname{rank}

是根的

\operatorname{rank}

值。

我们规定，

\operatorname{rank}

值相同的半树能进行

\operatorname{fair-link}

。操作之后，具有较大

key

的根

\operatorname{rank}+1

，其它结点不变。还是从论文拿的图 :

发现如果从若干只有一个结点的半树开始，不管怎样

\operatorname{fair-link}

，产生的半树的形态都是根的左子树挂着一个满二叉树。

更进一步，发现这样的半树跟二项树本质是相同的。画个图解释一下 :

(希望dalao们可以给我一个能做这样动图的软件qwq)

所以这个数据结构可以看作二项堆的优化。(Fib堆似乎也是qwq)

实际上论文似乎就是这么认为的。

但由于复杂度分析里面用到了半树上的兄弟，使用二项树的理论可能会很难受。

2.rp-heap的结构

rp-heap使用一个称为根链表的双向循环链表串起一串的半树根(但是实际上根链表存在仅仅是为了方便插入删除，并不表示任何顺序)，并且维护堆中有着最小值的结点的指针

H.min

。显然，

H.min

一定是某个根。

3.一个不够优秀的复杂度

对于

\operatorname{merge}

和

\operatorname{insert}

，我们直接连接/插入根链表。

对于

\operatorname{extract-min}

，和二项堆一样，把

H.min

删掉后，把它左子树的右链(或右脊柱，即从根一直走右儿子直到没有右儿子得到的路径)上所有边断开，得到若干棵半树(因为每个点都满足

\text{half-ordered}

，并且断开右链后右链上的点失去了右儿子)。将这个操作称为

\operatorname{disassembly}

(拆分)。

接下来把这些半树和根链表里的其它根一起进行一轮配对(

\text{One-pass link}

) : 对每个

\operatorname{rank}

建立一个桶，先遍历

\operatorname{disassembly}

产生的半树根再遍历根链表，把当前半树扔进对应的桶里。如果桶里已经有树，把它们

\operatorname{fair-link}

起来，并删掉根链表里面两棵树的根，直接在根链表加入

\operatorname{link}

后的新根。最后把桶里剩下的也扔进根链表。

对于

\operatorname{decrease-key}

，为了达到

O(1)

，我们用被减值的结点

x

的右子树替换它原来的位置，把它和它的左子树拿出来扔到根链表里，这个操作称为对

x

的一次

\operatorname{cut}

(切断)。这样我们才能不必让

x

上浮。

但是它破坏了

\operatorname{rank}

为

r

的二项树至少有

2^r

个结点的性质(你把一部分拆出来了，结点数就不够了)，因此可以造出

\operatorname{rank}

达到

\omega(\log n)

的半树，这样

\operatorname{extract-min}

就需要使用

\omega(\log n)

个桶。

这个东西可以摊到除了

\operatorname{extract-min}

是

O(\log n)

的(没有

\operatorname{decrease-key}

的情况下)，其它都是

O(1)

的，即不带

\operatorname{decrease-key}

的Pairing Heap复杂度。因为~~我看不懂英文~~这不是重点，所以这里不给出证明。有兴趣可以自行阅读论文。

为了得到高效的

\operatorname{decrease-key}

，我们需要放宽一些限制，使

\operatorname{rank}

是

O(\log n)

的性质不会被

\operatorname{decrease-key}

打破后难以复原，并在优秀的实现中保持该性质。

4.一个优秀的复杂度

定义

\Delta \operatorname{rank}(x)=\operatorname{rank}(\operatorname{fa}(x))-\operatorname{rank}(x)

，称左儿子

\Delta \operatorname{rank}

为

i

的点为一个

i

-结点，两个儿子

\Delta \operatorname{rank}

分别为

i,j

(不分顺序)的点为一个

i,j

-结点。

在之前的做法和标准的二项堆里，每个根是

1

-结点，每个内部结点是

1,1

结点。rp-heap的核心思想是放宽内部结点的限制。

我们引入两种

\text{rank rule}

，它们是rp-heap对半树

\operatorname{rank}

的限制。

Type-1(甲类)条件 : 每个根是

1

-结点，而每个内部结点要么是

1,1

-结点，要么是

0,?

-结点，其中

?

是任意正整数。可以发现一棵满足Type-1条件的

\operatorname{rank}

为

r

的半树至少有

2^r

个结点。

Type-2(乙类)条件 : 每个根是

1

-结点，而每个内部结点是

1,1

-结点，

1,2

-结点或

0,?

-结点，其中

?

是任意正整数。可以发现一棵满足Type-2条件的

\operatorname{rank}

为

r

的半树至少有

\text{Fibonacci}_ {r+2}\geq\phi^r

个结点。

因此不管使用哪一种

\text{rank rule}

，最大

\operatorname{rank}

是

O(\log n)

的。

这不会影响前面其它操作的正确性。

接下来我们可以尝试实现

\operatorname{decrease-key}

了。

如果被减值结点

x

是根，不用做任何结构操作。

否则，先对

x

进行一次

\operatorname{cut}

，并把

\operatorname{rank}(x)

设为

\operatorname{rank}(\operatorname{left}(x))+1

。然后从

x

原来的父亲开始，判断当前结点是否仍然满足

\text{rank rule}

，如果不满足，则把当前结点的

\operatorname{rank}

减少到满足，并继续处理当前结点的父亲。如果没有破坏条件就结束。

这是论文中的图 : (图中是Type-1 rp-heap)

现在你知道这个数据结构名字的由来了，它使用类似于配对堆的配对方式，并用特殊的

\text{rank rule}

来放松二项堆对结点

\operatorname{rank}

的限制，从而得到优秀的复杂度。

Fib堆也用到了类似的思想 : 在Fib堆里，如果一个结点要破坏使

\operatorname{extract-min}

复杂度正确的性质时，就把它也拆下来，并把拆下来这部分的复杂度摊掉。一会你将看到，rp堆也会摊掉保持

\text{rank rule}

的代价。

~~说句闲话，看看进度条~~

5.复杂度分析

下面的内容比较毒瘤~~并且有很多显然~~，请自行选择是否看完。不想看可以向下翻到代码部分。

这里只分析常数更小的Type-2 rp-heap。对Type-1有兴趣的话，~~反正我不会~~请自行阅读论文。

定义一个结点

u

的基本势(

\text{base potential}

)为，设

u

是一个

i,j

-结点(

u

只有一个儿子则视

j=0

)，则基本势为

i+j-1

，即

\Delta \operatorname{rank}(\operatorname{left}(u))+\Delta \operatorname{rank}(\operatorname{right}(u))-1

。

(这个译名是我口胡的，如果不标准，希望神仙们可以指出来)

定义一个结点

u

的额外势(

\text{extra potential}

)为 :

如果 $u$ 是根，额外势为 $1$ 。
如果 $u$ 是 $1,1$ -结点，额外势是 $-1$ 。
否则，额外势是 $0$ 。

(这个译名也是我口胡的，如果不标准，也希望神仙们可以指出来)

定义一个结点

u

的势为基本势和额外势的和。则立刻可得 :

如果 $u$ 是根，势为 $1$ 。
如果 $u$ 是 $1,1$ -结点，势为 $0$ 。
否则，设 $u$ 是 $i,j$ -结点，势为 $i+j-1$ 。

定义势函数为所有结点势的和。

\operatorname{merge}

和

\operatorname{find-min}

实际代价是

O(1)

的并且不改变势。

\operatorname{make-heap}

和

\operatorname{insert}

实际代价是

O(1)

的并且将势增加

1

。所以这四个操作摊还复杂度都是

O(1)

。

考虑

\operatorname{extract-min}

。定义

h

为

\operatorname{disassembly}

后半树的总数。显然，

\operatorname{extract-min}

的实际代价是

O(h+\log n)

(

\log n

是操作桶的时间，如果你每次最后遍历桶而不是记录非空桶的话)。考虑被删除根的左子树右链上最多有

\log_{\phi} n

个

1,1

-结点(每个使

\operatorname{rank}

减少

1

)，它们变成根之后会增加最多

\log_{\phi} n

的势。除此之外其它任何结点变成根都不会使势增加，所以

\operatorname{disassembly}

使势增加最多

\log_{\phi} n

。接下来进行一轮配对，在这

h

棵半树中最少进行

(h-\log_{\phi}n-1)/2

次

\operatorname{fair-link}

，每一次会把一个根变成

1,1

-结点，使势减少

1

，因此配对至少使势减少

(h-\log_{\phi}n-1)/2=h/2-O(\log n)

。整个操作使势增加最多

\log_{\phi}n-(h/2-O(\log n))=O(\log n)-h/2

。我们可以把势的单位增加到可以消去实际代价

O(h)

，因此摊还复杂度是

O(\log n)

。

接下来是恶心的

\operatorname{decrease-key}

。假设我们对

x

做了一次减值。

如果

x

是根，实际代价是

O(1)

并且不改变势。

否则，~~我们就懒得往下分析了~~ 定义

u_0=\operatorname{left}(x), u_1=x, u_i=\operatorname{fa}(u_{i-1})(1<i\leq k)

且

u_k

为在

\operatorname{decrease-key}

中维持

\text{rank rule}

时遇到的第一个不需要调整就满足

\text{rank rule}

的结点或是根(为根时是调整了根或根的儿子)，定义

v_i

为

\operatorname{decrease-key}

前

u_i

除

u_{i-1}

之外的儿子，即

u_{i-1}

的兄弟。加

\mathrm{'}

表示

\operatorname{decrease-key}

后的(真省事)(就是说，举个例子，

\operatorname{rank}

是

\operatorname{decrease-key}

前的

\operatorname{rank}

，

\operatorname{rank'}

是

\operatorname{decrease-key}

后的

\operatorname{rank}

)。

显然，这次操作的实际代价是

O(k)

。

显然，

\operatorname{decrease-key}

后势可能发生变化的只有

u_1,...,u_k

。

显然，

\operatorname{decrease-key}

后的结构变化只有

u_2

的原来是

u_1

的那个儿子变成了

v_1

，

u_1

变成了根并失去了右儿子。

先考虑基本势变化，即

u_1,...,u_k

的基本势变化。把它分成三部分。我们会在每部分最后列出一个式子，从它们可以推出关于基本势变化的结论。

考虑 $v_1,u_1,u_2,...,u_{k-1}$ 的 $\Delta \operatorname{rank}$ 和，在 $\operatorname{decrease-key}$ 前它们在同一条链上，中间的部分拆开相消，得到 $\operatorname{rank}(u_k)-\operatorname{rank}(v_1)$ 。

(说句闲话，这部分论文似乎出了点问题，把 $v_1$ 写成了 $v_0$ )

考虑 $v_1,u_2,u_3,...,u_{k-1}$ 的 $\Delta \operatorname{rank'}$ 和，在 $\operatorname{decrease-key}$ 后它们在同一条链上，中间的部分拆开相消，得到 $\operatorname{rank'}(u_k)-\operatorname{rank'}(v_1)$ 。

因为 $\operatorname{rank'}(v_1)=\operatorname{rank}(v_1)$ 且 $\operatorname{rank'}(u_k)\leq\operatorname{rank}(u_k)$ ， $\operatorname{rank'}(u_k)-\operatorname{rank'}(v_1)\leq\operatorname{rank}(u_k)-\operatorname{rank}(v_1)$ 。这部分的基本势减少了至少 $0$ 。(这是 $u_i$ 对 $u_{i+1}$ 的贡献， $\operatorname{decrease-key}$ 前 $v_1$ 对 $u_1$ 的贡献和 $\operatorname{decrease-key}$ 后 $v_1$ 对 $u_2$ 的贡献)
显然， $\Delta\operatorname{rank'}(u_0)=1\leq\Delta\operatorname{rank}(u_0)+1$ 。这部分的基本势减少了至少 $0$ 。(这是 $u_0$ 对 $u_1$ 的贡献)
因为 $u_i$ 被调整了而 $v_i$ 没有， $\Delta\operatorname{rank'}(v_j)\leq\Delta\operatorname{rank}(v_j)-1(2\leq j< k)$ 。因为 $u_k$ 不一定被调整了， $\Delta\operatorname{rank'}(v_k)\leq\Delta\operatorname{rank}(v_k)$ 。这部分的基本势减少了至少 $k-3$ 。(这是 $v_i$ 对 $u_i(2 \leq i)$ 的贡献)

我们已经计算了

u_1,...u_k

的每个儿子对它们的贡献。把它们加起来就得到基本势减少了至少

k-3

，即增加最多

3-k

。

然后考虑额外势变化。考虑额外势只会在

1,1

-结点变成其它结点时，或是某个结点变成根时增加

1

。

我们先证明在被调整的点中最多只有两个

1,1

-结点。考虑调整过程中遇到的第一个

1,1

-结点

u_j

，它会被调整为

1,2

-结点或

0,?

-结点。对于第一种，它的

\operatorname{rank}

没有改变，所以父亲的条件不会被破坏，所以它是最后一个被调整的结点，一共有一个

1,1

-结点。对于第二种，它的

\operatorname{rank}

减少了

1

，因此接下来所有需要调整点的

\operatorname{rank}

都只会减少

1

(不理解可以自己枚举情况)。接下来遇到的第二个

1,1

-结点只会被调整为

1,2

-结点，所以它是最后一个被调整的结点，一共有两个

1,1

-结点。因此，

1,1

-结点最多有两个，最多使额外势增加

2

。

在

\operatorname{decrease-key}

过程中，只有

u_1

变成了根，使额外势增加

1

。

把基本势和额外势的变化加起来，我们得到势的变化 : 势最多增加

6-k

。我们可以把势的单位增大到可以消去实际代价

O(k)

，所以

\operatorname{decrease-key}

的摊还复杂度是

O(1)

。

6.代码实现

请参考放在最前面的EtaoinWu的blog。

或者往下翻，是我自己写的代码，有注释。~~用指针没有可读性~~

优化Dijkstra到

O(n \log n+m)

是支持

O(\log n)

时间

\operatorname{insert}

和

\operatorname{extract-min}

，

O(1) \space\operatorname{decrease-key}

的堆的经典应用。

CPP

//Type-2 Rank-Pairing Heap优化Dijkstra
//luogu P4779(请自行调整MAXN和MAXM)

//没有merge操作，写起来大概也不难（

#define MAXN 100000
#define MAXM 1000000
#define Log_Phi_N 29

//点数，边数，桶数量

#ifndef NULL
#define NULL 0
#endif

#include<string.h>
#include<stdlib.h>
#include<stdio.h>

template<class T>

struct RP_Heap
{
	struct ListNode;
	struct Node
	{
		T val;
		int rank;
		Node *l,*r,*fa;
		ListNode* p;
		Node(){}
		Node(T _val,int _rank=0,Node* _l=0,Node* _r=0,Node* _fa=0):val(_val),rank(_rank),l(_l),r(_r),fa(_fa){}
	}t[MAXN+2],*p[MAXN+2],*min,*bucket[Log_Phi_N+1];
	int cnt,siz;
	bool has_min;
	struct ListNode
	{
		Node* ptr;
		ListNode *pre,*nxt;
	};
	struct List//手写链表
	{
		ListNode* head;
		
		List()
		{
			head=new ListNode();
			head->ptr=NULL;
			head->nxt=head;
			head->pre=head;
		}
		
		inline void insert(Node* _ptr)
		{
			ListNode* u=new ListNode();
			u->ptr=_ptr;
			u->pre=head;
			u->nxt=head->nxt;
			head->nxt->pre=u;
			head->nxt=u;
			_ptr->p=u;
		}
		
		inline void remove(ListNode* u)
		{
			u->pre->nxt=u->nxt;
			u->nxt->pre=u->pre;
			u->ptr->p=NULL;
			delete u;
		}
	}list;
	
	RP_Heap()
	{
		for(int i=0;i<MAXN;i++)
			p[i]=&t[i];//p[i]指向t[i]，便于分配空间
		has_min=0;//has_min让extract-min之后不用把min赋为-inf
		memset(bucket,0,sizeof(bucket));
	}
	
	inline Node* new_Node(T v)//这句话就是分配一个新结点，val为v的意思（
	{
		return ( & ( * p[cnt++] = Node(v,0,NULL,NULL,NULL) ) );
	}
	
	inline void swap(int &x,int &y){ int temp=x;x=y;y=temp; }
	inline int max(int x,int y){ return x>y?x:y; }
	inline int abs(int x){ return x>0?x:-x; }
	
	inline void swap(Node* &x,Node* &y){ Node* temp=x;x=y;y=temp; }
	
	inline Node* link(Node* u,Node* v)
	{
		if(v->val<u->val) swap(u,v);
		v->r=u->l;
		if(v->r)//记得判断是不是空指针，否则RE，以下类似的省略注释
			v->r->fa=v;
		u->l=v;
		v->fa=u;
		u->rank++;
		return u;
	}
	
	inline Node* update_min(Node* u)//更新min，为了写起来舒服，返回值是给的指针
	{
		if(!has_min||u->val<min->val)
			min=u,has_min=1;
		return u;
	}
	
	inline Node* insert(T _val)
	{
		Node* u=new_Node(_val);
		list.insert(update_min(u));//看出来update_min这么写舒服了qwq
		siz++;
		return u;
	}
	
	inline T find_min(){ return min->val; }
	inline int size(){ return siz; }
	inline bool empty(){ return siz==0; }
	
	inline void extract_min()
	{
		siz--;
		list.remove(min->p);
		has_min=0;
		int rk;
		Node *next_node,*u;
		ListNode *first=list.head->nxt;//第一个原有根位置
		for(u=min->l;u;u=next_node)//拆分左子树右链
		{
			next_node=u->r;
			u->fa=u->r=NULL;
			rk=u->rank;
			if(bucket[rk])//和桶里的合并，扔进根链表
				list.insert(update_min(link(u,bucket[rk]))),bucket[rk]=NULL;
			else//扔进桶
				bucket[rk]=u;
		}
		for(ListNode *i=first,*next_node;i!=list.head;i=next_node)
		{
			u=i->ptr;
			rk=u->rank;
			next_node=i->nxt;
			list.remove(i);
			if(bucket[rk])
				list.insert(update_min(link(u,bucket[rk]))),bucket[rk]=NULL;
			else
				bucket[rk]=u;
		}
		for(int i=0;i<=Log_Phi_N;i++)//遍历桶，把桶里的扔进根链表
			if(bucket[i])
				list.insert(update_min(bucket[i])),bucket[i]=NULL;
	}
	
	inline void decrease_key(Node* u,T key)//把u的值变成k(所以需要自己保证是减值不是增值)
	{
		u->val=key;
		if(u->fa==NULL)//是根，更新min直接返回
		{
			update_min(u);
			return;
		}
		if(u->l) u->rank=u->l->rank+1;//更新rank为左儿子rank+1
		else u->rank=0;//没有左儿子，说明是单点
		if(u->r) u->r->fa=u->fa;//把右儿子接到自己原来的位置
		if(u==u->fa->l) u->fa->l=u->r;
		else u->fa->r=u->r;
		int temp,lrk,rrk;
		for(Node* v=u->fa;v;v=v->fa)
		{
			lrk=v->l?v->l->rank:-1;//实现的小技巧，没有结点的rank视为-1
			rrk=v->r?v->r->rank:-1;
			temp=max(lrk,rrk)+(abs(lrk-rrk)<=1?1:0);//根据rank rule计算新的rank
			if(temp==v->rank)//如果没有改变rank，break掉
				break;
			v->rank=temp;
		}
		u->fa=u->r=NULL;//最后断开父亲和右儿子是因为前面循环开头要用右儿子，懒得再搞临时变量了
		list.insert(update_min(u));//插入根链表并更新min
	}
};

//下面的是Dijkstra模板

struct Edge
{
	int v,w,next;
}e[2*MAXM+2];

struct Node
{
	int u;
	int dis;
	inline bool operator<(const Node &x) const
	{
		return this->dis<x.dis;
	}
};

int h[MAXN+2],cnt=0;

inline void add_edge(int u,int v,int w)
{
	e[++cnt]={v,w,h[u]};
	h[u]=cnt;
}

int dis[MAXN+2];
int n,m,start,tu,tv,tw,to;

RP_Heap<Node> q;
RP_Heap<Node>::Node* node[MAXN+2];//对每个堆结点保留一个指针，才能进行decrease-key

inline void dij()//Dijkstra板子
//没有vis(表示是否已经扩展过的数组)是因为我们有decrease-key
{
	int now;
	for(int i=1;i<=n;i++)
		dis[i]=i==start?0:0x7fffffff,node[i]=q.insert({i,dis[i]});
	while(!q.empty())
	{
		now=q.find_min().u;
		q.extract_min();
		for(int i=h[now];i!=0;i=e[i].next)
			if(dis[e[i].v]>dis[now]+e[i].w)
				dis[e[i].v]=dis[now]+e[i].w,
				q.decrease_key(node[e[i].v],{e[i].v,dis[e[i].v]});//减值
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&start);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&tu,&tv,&tw),add_edge(tu,tv,tw);
	dij();
	for(int i=1;i<=n;i++)
		printf("%d ",dis[i]);
	return 0;
}

7.说在后面&更新记录

看到这篇blog的dalao们，如果发现了什么问题，希望可以告诉我qwq

2020/4/15 完结撒花qwq

upd 2020/4/16: 增加了代码，修改了一些细节。

upd 2020/4/17: 修改了一些细节。~~连更三天可见有多少bug~~

upd 2020/4/22: 修改了一处错误。

upd 2020/5/22: 修改了一些细节。

upd 2020/9/20: 修改了一处错误。

Rank-Pairing Heap(赋级配对堆)学习笔记

文章操作

0.一些记号

1.半树(half tree)

1.1.定义

1.2. $\operatorname{link}$

1.3. $\operatorname{rank}$ (级)

2.rp-heap的结构

3.一个不够优秀的复杂度

4.一个优秀的复杂度

5.复杂度分析

6.代码实现

7.说在后面&更新记录

相关推荐

评论

Rank-Pairing Heap(赋级配对堆)学习笔记

文章操作

0.一些记号

1.半树(half tree)

1.1.定义

1.2.link⁡\operatorname{link}link

1.3.rank⁡\operatorname{rank}rank(级)

2.rp-heap的结构

3.一个不够优秀的复杂度

4.一个优秀的复杂度

5.复杂度分析

6.代码实现

7.说在后面&更新记录

相关推荐

评论

1.2. $\operatorname{link}$

1.3. $\operatorname{rank}$ (级)