4 Leftist Heaps and Skew Heaps¶

文本统计：约 956 个字 • 28 行代码

4.1 Leftist Heaps¶

4.1.1 Definition and Property¶

Definition: 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 \(\text{Npl}(NULL) = –1\).

零路径怎么计算？

\[ \text{Npl}(X)=\min\{\text{Npl}(C)+1\ \text{for all C as children of X\}} \]

Definition: The leftist heap property is that for every node X in the heap, the null path length of the left child is at least as large as that of the right child.（左孩子的零路径比右孩子的零路径大）

Theorem: A leftist tree with \(r\) nodes on the right path must have at least \(2^r – 1\) nodes.

Proof:

当\(r\)为1时，这个左偏树至少有一个结点（为根节点）

当\(r=k+1\)时，左右孩子的右路径至多为\(k\)，左右孩子由归纳假设可知节点数至少\(2^k-1\)个节点，那么这棵树就至少有\(2^{k+1}-1\)个节点，由此归纳成立。

4.1.2 Merge operation¶

Structure:

struct TreeNode 
{ 
    ElementType     Element;
    PriorityQueue       Left;   
    PriorityQueue       Right;
    int         Npl;
} ;

Merge的大体思路是将右路径分拆开来按照从小到大先依次装起来，然后再沿着右路径依次调整成左偏树。当然这个是手动地去合并时可以这样操作，写程序的时候使用递归的方法

Step 1: \(Merge(H_1\rightarrow Right,H_2)\)

Step 2: \(Attach (H_2,H_1\rightarrow Right)\)

Step 3: \(Swap(H_1\rightarrow Right,H_1\rightarrow Left)\) if necessary

PriorityQueue  Merge ( 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;
}

算法复杂度：\(O(\log N)\)

4.1.3 DeleteMin¶

Step 1: Delete the root
Step 2: Merge the two subtrees

算法复杂度：\(T_p=O(\log N)\)

4.2 Skew Heaps¶

4.2.1 Definition and operations¶

目标：Any M consecutive operations take at most \(O(M\log N)\) time

Merge: Always swap the left and right children except that the largest of all the nodes on the right paths does not have its children swapped. (Not really a special case, but a natural stop in the recursions递归终点的条件)

还是将两个堆按照右路径拆开，然后将左子树甩到右子树然后拼接起来，但是如果只剩下的部分只属于一个堆了，那么我们就可以直接不变直接接上去。

而当我们用循环来实现的时候，只有右路经最大的那个节点是不转的，其余都是转的。

与Leftist heap的区别在于不用严格遵守Leftist heap的特征，取而代之的就是合并的时候将左子树放到右边再合并。

Insert operation

我们可以把它看成原先的堆与仅有插入元素的堆合并

4.2.2 Merge的均摊时间¶

现在我们研究merge的均摊时间

首先需要定义一些概念：

定义重结点（heavy）为右子堆结点数大于左子堆结点数的结点，否则为轻结点。
定义右路径为一直往右走的路径。
定义势能\(\Phi(i)\)为第i次合并后重结点的个数之和。

考虑第i次合并过程，比如堆a，和堆b。它们右路径上轻、重点个数分别为 \(l_a\), \(h_a\) 和 \(l_b\), \(h_b\)。那么这次合并的实际开销为

\[ c_i=l_a+h_a+l_b+h_b \]

本次合并之后，在右路径上，一个重结点右儿子本来就比左儿子重，合并又发生在右儿子，交换后左儿子大于右儿子，所以合并后重结点一定会变轻结点。考虑最坏情况，所有轻结点都变成重结点。并且由于轻结点的性质，一条右路径上的轻结点的数量小于\(\lg n\)。

所以本次合并过程的势能变化为

\[ \Delta \Phi<l_a+l_b−h_a−h_b \]

均摊开销等于势能变化加上实际开销

\[ \begin{align*} \hat c_i&=\Delta \Phi+c_i\\&<2(l_a+l_b)\\&<2\lg n \end{align*} \]

其中这个n指的是合并后堆中节点的个数。

对于插入也是同样的道理，看成特殊的合并即可。

评论区

对你有帮助的话请给我个赞和 star =>

欢迎跟我探讨！！！