Leftist Heaps 习题解高级数据结构学习笔记

Leftist Heaps （最左堆）是一种用于快速合并的数据结构，是堆的一种变种。它的合并操作只需花费O(logN)的代价。
对于二叉堆来说，两个堆合并是非常昂贵的操作，这将耗费O(N)的时间，与重新建堆的时间相同。为了应对优先队列的Merge操作，我们从本篇开始将介绍包括最左堆（又叫左式堆）在内的三种数据结构。
本篇将介绍相关题目。

证明二叉堆的合并需要耗费O(N)的代价
二叉堆合并操作是通过将一个堆的元素依次插入另一个堆完成的。我们知道，堆的插入平均花费常数时间代价。我们考察两个都是N大小的堆的合并，那么我们一共进行N次插入，花费O(N)的代价。

题目

Merge the two leftist heaps in the following figure. Which one of the following statements is FALSE? (3分)

文章图片

A. 2 is the root with 11 being its right child
B. the depths of 9 and 12 are the same
C. 21 is the deepest node with 11 being its parent
D. the null path length of 4 is less than that of 2

文章图片

merge操作是这样的：

Merge(MinRoot{T1, T2}, The other tree)
我们记Merge的前一个参数为H1，后一个参数为H2。若H1的左儿子为空，则将H2作为H1左子树。否则合并H1的右子树与H2。
合并后检查是否满足定义，否则交换。
伪代码描述如下：

PriorityQueueMerge ( PriorityQueue H1, PriorityQueue H2 ) { if ( H1 == NULL )return H2; if ( H2 == NULL )return H1; if ( H1->Element < H2->Element )return Merge1( H1, H2 ); else return Merge1( H2, H1 ); }static PriorityQueue Merge1( PriorityQueue H1, PriorityQueue H2 ) { if ( H1->Left == NULL )/* single node */ H1->Left = H2; /* H1->Right is already NULL and H1->Npl is already 0 */ else { H1->Right = Merge( H1->Right, H2 ); /* Step 1 & 2 */ if ( H1->Left->Npl < H1->Right->Npl ) SwapChildren( H1 ); /* Step 3 */ H1->Npl = H1->Right->Npl + 1; } /* end else */ return H1; }

【Leftist Heaps 习题解】所以我们按如图方式进行合并，得到最后的那棵树。D选项中4和2的npl都是2。故选D。

[Definition] Npl(X)
The null path length, Npl(X), of any node X is the length of the shortest path from X to a node without two children. Define Npl(NULL) = –1.
也就是说，npl是从该节点到第一个没有两个孩子的子节点的路径长度。

答案为D

We can perform BuildHeap for leftist heaps by considering each element as a one-node leftist heap, placing all these heaps on a queue, and performing the following step: Until only one heap is on the queue, dequeue two heaps, merge them, and enqueue the result. Which one of the following statements is FALSE? (3分)
A. in the k-th run,?N/2k?leftist heaps are formed, each contains2knodes
B. the worst case is whenN=2Kfor some integer K
C. the time complexityT(N)=O(N2log20+N22log21+N23log22+...+N2Klog2K?1for some integer K so thatN=2K
D. the worst case time complexity of this algorithm is Θ(NlogN)

这里主要证明D选项是FALSE：
T(N)=O(N2log20+N22log21+N23log22+...+N2Klog2K?1
=O(N2log2×0+N22log2×1+N23log2×2+...+N2Klog2×(K?1)
=N?log2?(122+223+...+k?12k)
括号内的和我们可以通过错位相减法求出，于是式子化为
=N?log2?(1?k+12k)
k+12k 在N趋近无穷大时为0
故时间复杂度为O(N)