Background

在堆的合并中，仅仅只是拷贝都需要 的时间复杂度，所以希望提出一种更好的数据结构，让堆的合并的效率更高

Definition

外节点

只有一个儿子或没有儿子的节点，即左右儿子至少有一个为空节点的节点。

距离/零路长

距离/零路径长 null path length ： 定义为 X 结点到它的后代中离它最近的外结点的最短路径长度，即两结点之间路径的权值和。特别的，外结点的距离为 0 ，空结点的距离为 。

左式堆

左偏树/左式堆：一种满足左偏性质的堆有序的二叉树，其左偏性质体现在左儿子的距离大于等于右儿子的距离。即对于任意一个节点，

左式堆的距离

左偏树/左式堆的距离：我们将一棵左偏树根结点的距离作为该树的距离。

合并操作

  • 如果两个堆中有一个堆为空，就直接返回另一个堆。
  • 否则为了合并两个堆，需要比较它们的根。
    • 将具有大的根值的堆H2与具有小的根值的堆H1的右子堆H3合并得到一个新的左式堆，其中H2和H3的合并也采用同样的逻辑。

合并代码示例

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
void LeftistHeap::merge(LeftistHeap &rhs) {
	if (this == &rhs) return; 
	root = merge(root, rhs.root); 
	rhs.root = nullptr;            
}

LeftistNode *merge(LeftistNode *h1, LeftistNode *h2) {
	if (h1 == nullptr) return h2;
	if (h2 == nullptr) return h1; 
	if (h1->element < h2->element) 
		return merge1(h1, h2); 
	else 
		return merge1(h2, h1);
} 
LeftistNode *merge1(LeftistNode *h1, LeftistNode *h2) {
	if (h1->left == nullptr) 
		h1->left = h2; 	     
	else {
		h1->right = merge(h1->right, h2);
		if (h1->left->dist < h1->right->dist) 
			swapChildren(h1);
		h1->dist = h1->right->dist + 1;
	}
	return h1;
}

插入操作

左式堆的插入就是新建一个只有一个节点的左式堆再和原来的合并

1
2
3
void insert(const Comparable &x) {
root = merge(new LeftistNode(x), root); 
}

删除操作

删除的本质就是删除根节点，得到左右两个子树的两个堆再做合并

1
2
3
4
5
6
7
8
9
10
11
void deleteMin() {
	if (empty()) throw underflow_error("LeftistHeap Empty");
	LeftistNode *oldRoot = root;
	root = merge(root->left, root->right);
	delete oldRoot;
}

void deleteMin(Comparable &minItem) {
	minItem = findMin();
	deleteMin();
}

时间复杂度分析

以上三个操作的复杂度都依赖于合并操作，其复杂度均为

相关文章

[[Heap]]