左式堆

缘起

【1】中我们介绍了优先队列以及它的一种实现——堆. 其实又叫二叉堆. 因为它的结构是完全二叉树. 而这里介绍的是优先队列的另一种实现方式——左式堆（left heap）. 它的引入是为了满足堆结构之间的合并这种基本操作.

如上图，小根堆A和小根堆B需要合并成为小根堆H（假设A的元素个数n>=B的元素个数m）. 如果使用【1】中的二叉堆实现的话，不难想象以下两种思路

  1. 反复取出B中的元素插入A中，复杂度为 m(O(logm)+O(log(m+n))) = O(mlogn)
  2. 将A和B重新打散来建堆，使用floyd算法，复杂度是O(n+m)=O(n).

综上，如果基于二叉堆实现堆的合并的话，复杂度为 min(O(n), O(mlogn)). 其实，这种性能是会被质疑的——因为A和B本身已经有某种偏序关系了. 不应该还像完全独立的情形（floyd建堆）那种复杂度.

那有木有更快的算法呢? 于是左式堆横空出世了. 其实你想想看，为什么用二叉堆合并速度一定会带上O(n), 就是因为参与合并的元素数量不能尽量少.

为此，不妨首先打破此前形成的错觉并大胆质疑： 堆是否也必须与二叉搜索树一样，尽可能地保持平衡？ 值得玩味的是，对于堆来说，为控制合并操作所涉及的节点数，反而需要保持某种意义上的“不平衡”！

所以实际上，本文介绍的左式堆不仅仅不是平衡二叉树，而且是非常不平衡的二叉树!!! 正因为远离平衡二叉树，所以实际上我们并不推荐使用数组实现左式堆结构. 而推荐使用链表.

1
2
3
4
5
左式堆的定义如下

1. 它是二叉树
2. 它满足堆结构，即大根堆或者小根堆.
3. 任何节点的左孩子的npl>=右孩子的npl, 因此，任意节点的npl=右孩子的npl+1,这个性质使得它不是一棵理想平衡树，因为它显然偏重于使树向左增加深度。

节点的npl（null path length）的定义是此节点所有到不具有两个儿子的节点的路径中的最短路径长.

例如

​ 图1

上图左边的根节点的npl是1——因为根节点往右边走就对了. 特别的，本身就没有两个儿子的节点的npl值是0.

方便起见，规定null节点的npl是 -1.

图1的右边不是左式堆，左边是左式堆，因为右边的带 * 的节点的左孩子的npl=0, 右孩子的npl=1

不难知道左式堆的如下几个性质

  1. 对于左式堆的任意一个节点只能有三种情况，有两个子节点、没有子节点、仅有一个节点且该节点为左子节点。也就是说，如果存在任意一个节点只有右节点，那么这个堆一定不是左式堆。但是，如果一个节点每个节点都满足上面的条件，它不一定是左式堆，还需要满足零路径长的条件(图1的右边就满足，但是不是左式堆, 即这只是必要不充分条件)。
  2. 沿左式堆的右路径（即一路向右）是该堆中的最短路径。否则，就会存在某个节点 X 的左儿子的最短路径长小于右儿子的最短路径长。

给出如下左式堆的算法. 后面给出证明为什么此算法是正确的. 下面的左式堆以大根堆为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include "stdafx.h"
#include <iostream>

using namespace std;
const int INF = 0x3f3f3f3f;

typedef struct LeftHeapNode // 左式堆节点
{
	LeftHeapNode *left, *right; // 左右孩子
	int data; // 数值
	int npl; // 该节点的npl值

	LeftHeapNode(int data):left(0), right(0), data(data),npl(0){}

}LeftHeapNode, *LeftHeap; // 左式堆

void swap(LeftHeap node) // 交换node的左子树和右子树
{
	LeftHeap t = node->left;
	node->left = node->right;
	node->right = t;
}

LeftHeap merge(LeftHeap, LeftHeap);
LeftHeap merge1(LeftHeap, LeftHeap);


LeftHeap merge1(LeftHeap node1, LeftHeap node2) // 合并两个非null节点 node1和node2，而且是将node2合并到node1上去
{
	if (!node1->left) node1->left = node2; // 如果node1左子树是空树（则右子树必然也是空树，因为左孩子的npl是-1, 不然就违背了左式堆的定义，即node1就是一个光杆司令）, 注意， 无需更新node1的npl, 因为依旧是0啊~
	else
	{
		node1->right = merge(node1->right, node2); // 因为不能保证node1的右子树是否为空, 所以只能调用merge，而不能递归调用merge1
		if (node1->left->npl < node1->right->npl) swap(node1); // 如果node1的右子树和node2合并之后npl值和node1的左孩子的npl值违背了左式堆定义, 则简单交换一下左右子树即可
		node1->npl = node1->right->npl + 1; // 更新npl，用到了左式堆的定义3
	}
	return node1;
}


LeftHeap merge(LeftHeap root1, LeftHeap root2) // 合并左式堆
{
	if (!root1) return root2;
	if (!root2) return root1;
	return root1->data > root2->data ? merge1(root1, root2): merge1(root2, root1);
}

int _max(LeftHeap root) {return root->data;} // 取得堆中的最小值(因为左式堆依旧是堆)

LeftHeap insert(LeftHeap root, int data) // 建堆的时候用——将data的数值插入左式堆
{
	LeftHeap node = new LeftHeapNode(data);
	return merge(root, node);
}

LeftHeap build(int *a, int n) // 使用数组a[0,...,n) 建(左式)堆
{
	LeftHeap root = 0;
	for (int i = 0; i<n;i++) root = insert(root, a[i]);
	return root;
}

int pop(LeftHeap &root) // 移除左式堆中的最小元素, 并返回最小元素
{
	if (!root) return -INF; // 空集的最大值是-INF
	int ret = root->data;
	root = merge(root->left, root->right); // 调整左式堆
	return ret;
}


int main()
{
	int a[] = {21,10,14,23,17,26,3,8};
	int b[] = {12,33,24,18,37,7,18,6};
	LeftHeap h1 = build(a, sizeof(a)/sizeof(int)); // 两个左式堆
	LeftHeap h2 = build(b, sizeof(b)/sizeof(int));
	LeftHeap root = merge(h1, h2);
	cout << _max(root) << endl;
	cout << pop(root) << endl;
	return 0;
}

左式堆合并算法的正确性（左式堆其实就是这个合并算法，其他都只是这个合并算法的平凡推论）

就是数学归纳法. 其实我们主要就是验证 merge1的正确性

如果right和node2合并成为一个左式堆（注意，这是归纳假设，归纳起步就不验证了，那是trival的）. 那么只需要证明按照merge1算法得到的node1也是一个左式堆. 这几乎是显然的. 首先, node1>node2 && node1>left && node1 > right, 所以一定符合大根堆定义. 其次，因为如果合并之后不满足npl条件的话，则做了交换操作，所以node1也是满足npl限制的. 综上，我得到了一个更大的左式堆——node1. 所以左式堆算法merge 正确.

左式堆的合并复杂度

因为取决于右子树节点个数，所以合并算法的复杂度是O(logn), 比原先二叉堆实现的堆结构合并操作快了一个数量级. 所以正应验了那句老话——没有最完美的，只有最合适的~

分析

参考

【1】https://yfsyfs.github.io/2019/05/25/%E5%A0%86%E6%8E%92%E5%BA%8F/