week3¶

Leftist heap（左式堆/左倾树）¶

null path length(npl):从节点到NULL的最短路径。规定npl(NULL)=-1,npl(leaf)=0。

左偏树：满足最小（大）堆的性质（但不是完全二叉树），并对任意节点x,npl（left child）>=npl(right child)

以下以最小堆为例子。

性质¶

定理：right path有r个节点，那么左偏树至少有\(2^r-1\)个节点

merge¶

merge是核心操作，以下是递归的实现：

如果两个堆中至少有一个是空的，那么直接返回另一个即可；
如果两个堆都非空，我们比较两个堆的根结点key的大小，key小的是H1，key大的是H2；
如果H1只有一个顶点（根据左式堆的定义，只要它没有左孩子就一定是单点），直接把H2放在H1的左子树就完成任务了（很容易验证这样得到的结构符合左式堆性质，此时Npl也没有变化）；
如果H1不只有一个顶点，则将H1的右子树和H2合（这是递归的体现）
如果 H1 的Npl 性质被违反，则交换它的两个子树；
更新 H1 的Npl，结束任务.

Heap merge(Heap H1,Heap H2){
    if(H1==NULL){
        return H1;
    }
    if(H2==NULL){
        return H2;
    }
    if(H1->key<H2->key){
        return merge1(H1,H2);
    }else{
        return merge1(H2,H1);
    }
}

Heap merge1(Heap H1,Heap H2){
    if(H1->left==NULL){
        H1->left=H2;
    }else{
        H1->right=merge(H1->right,H2);
        if(H1->left->npl<H1->right->npl){
            swap_children(H1);
        }
        H1->npl=H1->right->npl+1;
    }
    return H1;
}

以下是迭代版本： 1. 比较根节点大小，把根节点大小较小的作为根节点并保留其左子树。 2. 继续迭代比较他的右子树和剩下的堆的根节点大小，重复步骤1直到结束 3. 以此检查右路径的每一个节点的npl并做相应修复

可以发现，递归的最大深度是两个堆的右路径长度之和，那么T=O(logN)。

insert¶

视为将一个堆与一个单个节点的merge

deletemin¶

先删除根节点，然后merge两个子堆

skew heap（斜堆）¶

与liftist heap相比，不需要维护npl的性质，merge操作无脑交换左右子树即可，以下是注意的点：

在 base case 是处理 H 与null 连接的情况时，左式堆直接返回H 即可，但斜堆必须看H 的右路径，我们要求H 右路径上除了最大结点之外都必须交换其左右孩子。
在非 base case 时，若 H1 的根结点小于 H2，如果是左式堆，我们需要合并 H1 的右子树和 H2作为H1 的新右子树，最后再判断这样是否违反性质决定是否交换左右孩子，斜堆直接无脑交换，也就是说每次这种情况都把H1 的左孩子换到右孩子的位置，然后把新合并的插入在H1的左子树上。

摊还分析¶

定义：我们称一个结点P是重的（heavy），如果它的右子树结点个数至少是P的所有后代的一半（后代包括P自身）。反之称为轻结点（light node）。

引理：对于右路径上有l个轻结点的斜堆，整个斜堆至少有\(2^l−1\)个结点，这意味着一个n个结点的斜堆右路径上的轻结点个数为O(logn)。

证明：对于l=1显然成立，现在设小于等于l都成立；

对于l+1的情况，我们找到右路径上第二个轻结点，那么它所在子树大小根据归纳假设至少有\(2^l−1\)个结点。现在考虑第一个轻结点，根据轻结点定义它的左子树更大，而右路径上第二个轻结点所在的子树在其右子树中，因此它的左子树至少有\(2^l−1\)个结点。故整个堆至少有\(1+(2^l−1)+(2^l−1)=2^{l+1}−1\)个结点。

摊还分析：若我们有两个斜堆H1和H2，它们分别有n1和n2个结点，则合并H1和H2的摊还时间复杂度为O(log(n1+n2)).

证明：定义势能函数D(x)=x的重节点个数。分析merge操作,设\(H_1,H_2\)合成\(H_3\)；\(h_i,l_i\)为\(H_i\)的右路径上的重，轻节点个数,有：\(\hat{c}=c+D(H_3)-[D(H_1)+D(H_2)]\)。

\(D(H_1)+D(H_2)=h_1+h_2+h\),h为所有不在右路径上的重节点。

可以发现，只有右路径上的轻重节点才可能改变，同时，由于斜堆每次交换左右子树，那么重节点一定会变成轻节点，轻节点可能变成重节点，即：\(D(H_3)\leq h+l_1+l_2\).

\(c=l_1+l_2+h_1+h_2\),代入得：\(\hat{c} \leq 2(l_1+l_2)=O(logN_1+logN_2)=O(log(N_1+N_2))\)