Lec 4: Leftist Heaps and Skew Heaps⚓︎

Leftist Heaps⚓︎

Definition⚓︎

左偏堆（又称左式堆、左倾堆等）(leftist heaps)

• 具有与一般的堆一致的顺序性质，即每个节点一定比它所有的孩子节点大 / 小
• 变化之处在于结构性质：它不再是一棵完全二叉树，而是一棵不平衡的树

除此之外，左偏堆的节点还多了一个名为空指针路径长度(null path length) 的字段，记作 \(\mathrm{Npl}(X)\)，表示的是从节点 \(X\) 到没有两个孩子的节点（即叶节点或度为 1 的节点）的最短距离。定义 \(\mathrm{Npl}(NULL) = -1\)。这个字段用于准确表述左偏堆满足的性质：对于堆上的每个节点，它的左孩子的空指针路径长度不小于它的右孩子的空指针路径长度，因此整棵树会“向左歪”，即左子树的深度更深一些。空指针路径长度的递推关系式为：

因此，空指针路径长度往往是自底向上计算的。

由这个定理，不难得到以下推论：对于一个具有 \(N\) 个节点的左偏堆，它的右侧路径上至多有 \(\lfloor \log (N + 1) \rfloor\) 个节点。因此，想要减小合并操作所花的时间，我们需要让该操作尽可能地在堆的右侧来完成，因为右侧的堆高为 \(O(\log N)\)，那么合并的速度就能接近 \(O(\log N)\) 了。

Operations⚓︎

左偏堆的声明如下：

#ifndef _LeafHeap_H

struct TreeNode;
typedef struct TreeNode * PriorityQueue;

// Minimal set of priority queue operations
// Note that nodes will be shared among several
// leftist heaps after a merge; the use must
// make sure to not use the old leftist heaps

PriorityQueue Initialize(void);
ElementType FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2);

#define Insert(X, H) ( H = Insert1((x), H) )
// DeleteMin macro is omitted

PriorityQueue Insert1(ElementType X, PriorityQueue H);
PriorityQueue DeleteMin1(PriorityQueue H);

#endif

// Place in implementation file
struct TreeNode {
    ElementType   Element;
    PriorityQueue Left;
    PriorityQueue Right;
    int           Npl;
};

接下来主要介绍左偏堆合并操作的实现。

Merge⚓︎

Recursive Version

现在我们需要合并这两个左偏堆：

递归版本的合并操作流程如下：

1. 合并：Merge(H1->Right, H2)

   • 由于 \(H_1\) 的根节点更小，所以我们将 \(H_1\) 的右子树与 \(H_2\) 进行递归地合并
   

2. 附加：Attach(H2, H1->Right)

   • 将合并好的堆附加到 \(H_1\) 右子树的位置
   

3. 如有必要，交换左右子树：Swap(H1->Right, H1->Left)

   

PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2) {
    // If one heap is empty, then return another heap
    if (H1 == NULL) {  
        return H2;
    }
    if (H2 == NULL) {
        return H1;
    }
    // Assure that the left parameter is the heap with smaller root
    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;      // Important!
    }
    return H1;
}

Iterative Version

迭代版本的合并操作流程如下（还是以上面那两个堆为例）：

1. 在不改变左孩子的情况下，根据两个堆的右子树进行合并。我的理解是：

   • 确定将根节点较小的堆作为合并的目标堆，然后将目标堆的右子树“拆出来”，作为待比较堆 A，另一个堆作为待比较堆 B
   • 比较两个待比较堆，将根节点更小的待比较堆去掉右子树后附加到目标堆的右子树（即最右侧），形成新的目标堆，该目标堆的最右侧是空的
   • 而被抛下的右子树作为新的待比较堆，与另一个待比较堆进入下一轮的 PK。重复进行上述的比较、附加操作，直到只剩下一个目标堆为止

   实际上，最开始的目标堆也是一个待比较堆。

   动画演示

   初始状态 Step 1 Step 2 Step 3 Step 4

   

   \(H_1\) 的根节点更小，因此 \(H_1\) 作为目标堆，它的右子树从它身上分离开，作为待比较堆，\(H_2\) 则作为另一个待比较堆。

   

   由于 \(H_2\) 的根节点更小，所以将 \(H_2\) 的根节点及其左子树附加在 \(H_1\) 右子树的位置上，这样就形成了新的目标堆。而 \(H_1\) 与 \(H_2\) 原来的右子树则作为新的一组待比较堆。

   

   由于 \(H_2\) 原来右子树上的根节点更小，因此将它的根节点及其左子树附加在目标堆最右侧的位置上。剩下的原 \(H_1\) 右子树和 \(H_2\) 右子树的右子树作为新的待比较堆。

   

   由于 \(H_1\) 原来右子树上的根节点更小，因此将它的根节点及其左子树附加在目标堆最右侧的位置上。此时仅剩下原 \(H_2\) 右子树的右子树。

   

   将剩余的堆附加在目标堆的最右侧，合并操作完成。

2. 如有必要，交换合并后的堆的两个子树

   

递归实现和迭代实现各有优劣：

• 递归实现的难度较小，代码写起来较为容易，但是不太好让人理解合并的过程
• 迭代实现更为清晰地展现了合并的过程，但是代码编写较为困难

无论是递归实现，还是迭代实现，时间复杂度均为 \(T_P = O(\log N)\)

Insert⚓︎

插入是一种特殊的合并操作，可以理解为只有一个节点的堆与另一个堆进行合并。

PriorityQueue Insert1(ElementType X, PriorityQueue H) {
    PriorityQueue SingleNode;

    SingleNode = (PriorityQueue)malloc(sizeof(struct TreeNode));
    if (SingleNode == NULL) 
        FatalError("Out of Space!!!");
    else {
        SingleNode->Element = X;
        SingleNode->Npl = 0;
        SingleNode->Left = SingleNode->Right = NULL;
        H = Merge(SingleNode, H);
    }
    return H;
}

DeleteMin⚓︎

我们可以利用合并操作来删除最小节点：

1. 删除根节点，此时会将原来的堆拆作两个子堆
2. 合并两个子堆

// DleteMin1 returns the new tree;
// To get the minimum, use FindMin
// This is for convenience

PriorityQueue DeleteMin1(PriorityQueue H) {
    PriorityQueue LeftHeap, RightHeap;

    if (IsEmpty(H)) {
        Error("Priority queue is empty");
        return H;
    }

    LeftHeap = H->Left;
    RightHeap = H->Right;
    free(H);
    return Merge(LeftHeap, RightHeap);
}

时间复杂度：\(T_P = O(\log N)\)

DecreaseKey⚓︎

在介绍二叉堆的时候，我们用DecreaseKey()函数使堆中的某个元素移到根节点上，以此提高该元素的优先级。在左偏堆中，这样的操作虽然麻烦一些，但是时间复杂度仍然为 \(O(\log N)\)。

实现步骤：

• 将被操作的节点 \(K\) 及其子树从原来的堆中剔除
• 将刚刚提出来的子树分为 3 部分：节点 \(K\)、左子树和右子树，合并左右子树（\(O(\log N)\)），形成新的子树 \(S\)
• 将 \(S\) 插入回原来堆内节点 \(K\) 的位置，不断调整该子树祖先的 \(Npl\) 值，直到遇到某个不需要改变 \(Npl\) 值的节点为止
  • 何时需要调整 \(Npl\) 值：（待补充）
• 将节点 \(K\) 作为根节点插入到这个堆内，它的 \(Npl\) 值为 0

BuildHeap⚓︎

构建左偏堆的时间复杂度为 \(O(N)\)，有以下几种实现方法：

• 递归构建左子树和右子树，然后将根节点“下滤”
• 将每个元素看作单节点的左偏堆，先将它们全部放在一个队列里，然后重复以下操作：让队首的两个堆出队，将它们合并起来后将这个新的堆入队，直到只剩下一个堆为止

Skew Heaps⚓︎

Definition⚓︎

斜堆(skew heaps) 是左偏堆的一种简单形式，它们之间的关系类似 AVL 树和伸展树。斜堆去除了Npl字段，但它像伸展树一样，能够保证在 \(M\) 次连续操作消耗至多 \(O(M \log N)\) 的时间。

斜堆的合并操作的大致思路类似左偏堆，但不同之处在于：由于斜堆不维护Npl字段，因此即将被附加的待比较堆（它的根节点更小，包括最开始的目标堆）在拆开右子树后，需要把待比较堆的左子树换到右子树的位置上，然后再加到目标堆上。也就是说每一次的附加都需要一次交换操作，而不是最后根据Npl的情况来交换。

动画演示

这里的动画我就不逐帧分析了，相信大家在学习左偏堆的合并，以及斜堆合并的思路后，应该比较容易看懂这个动画 ~

Lucky CaseUnlucky Case

这里运气比较好，这么一番简单的操作后还能保证左偏的性质，但运气可不总是那么好，请看后面的例子。

很明显，合并后的堆更加偏向右侧，因此这不是一个符合要求的堆。

Amortized Analysis⚓︎

由于插入和删除本质上还是合并操作，所以这里我们就讨论合并操作的均摊复杂度，结论是：\(T_{\mathrm{amortized}} = O(\log N)\)，下面我们就来证明这个复杂度。

证明

均摊分析的三种方法中，势能分析法最为强大，因此我们使用这个方法。势能分析法中最重要的便是确定势能函数：我们令第 \(i\) 次操作后的数据集 \(D_i\) 为目标堆的根节点，势能函数 \(\Phi(D_i)\) 为这个堆上重节点(heavy node) 的个数。

所谓「重节点」，指的是满足右子树的节点个数占整棵树节点个数（包括这个根节点）的一半以上的节点。对应的也有「轻节点」的概念，即不是重节点的节点。

为什么势能函数不是右子树的节点个数

我们知道，斜堆会不停地交换左右子树，因而右子树的节点个数有可能会增加，这是不好的情况；但是在好的情况下，右子树的节点个数也不会减少。这导致势能函数只能反映不好情况下堆的变化，而无法体现好的情况，而一个好的势能函数应当同时反映数据结构的好坏，因此简单记录右子树的节点个数不能满足均摊分析的要求。

而重节点个数很好地反映了当前斜堆的情况：情况较差时，重节点个数多；情况较好时，重节点个数少，可用于“抵消”情况较差的情况，因而更适合作为势能函数。

例子

初始状态合并后

我们用灰色阴影标出重节点，其他节点都是轻节点。可以看到，左边堆的 6、9，以及右边堆的 1 都是重节点。

将两个堆合并后，发现有些节点依然保持原来的轻重状态，但是也有部分节点的轻重状态发生转化，这里用红色箭头指出了发生变化的节点：原来的重节点 1 变成了轻节点，而原来的轻节点 8 变成了重节点

结论：合并后轻重状态发生变化的节点一定位于原来堆上的（最）右侧路径。理由是在斜堆的合并过程中，待比较堆的根节点一定是原来两个堆上（最）右侧路径的节点（理解了斜堆的合并操作后不难想到），而其他路上的节点基本维持原有的样子不变。

因此，我们在势能分析的时候更关注右侧路径上的节点（无论轻重）。记 \(H_i = l_i + h_i(i = 1, 2)\)，其中 \(H_i, l_i\) 和 \(h_i\) 分别表示右侧路径的节点数，右侧路径上的轻节点数和重节点数。所以在最坏情况下，合并所需时间为：

\[ T_{\mathrm{worst}}= l_1 + h_1 + l_2 + h_2 \]

• 在合并之前，势能函数 \(\Phi_i = h_1 + h_2 + h\)，其中 \(h\) 为两个堆内剩余的重节点数
• 在合并之后，势能函数 \(\Phi_{i+1} \le l_1 + l_2 + h\)
  • 原因：由上面的结论知，两个堆右侧路径的节点的轻重状态可能会发生改变，最坏的情况是：原来两个堆右侧路径上的节点都是轻节点，合并之后都变成了重节点，所以合并后的堆的重节点个数最多为 \(l_1 + l_2 + h\)

所以，

\[ \begin{align} T_{\mathrm{amortized}} & = T_{\mathrm{worst}} + \Phi_{i+1} - \Phi_i \notag \\ & = 2(l_1 + l_2) \notag \end{align} \]

由于 \(l = O(\log N)\)，所以均摊复杂度 \(T_{\mathrm{amortized}} = O(\log N)\)。证毕。

补充：证明 \(l = O(\log N)\)

注：\(l\) 是堆（最）右侧路径的轻节点数

我们可以先证明：对于右侧路径上带右 l 个轻结点的斜堆，至少有 \(2^l - 1\) 个结点。换句话说，如果一个堆有 \(N\) 个节点，那么它右侧路径上的轻节点个数为 \(O(\log N)\)，即 \(l = O(\log N)\)，所以只要证出前者，后者自然成立。我们采用归纳法证明（证明过程类似左偏堆那个定理的证明）：

• 当 \(l = 1\) 时，显然成立
• 假设 \(l \le n\) 时，该结论成立
  • 那么当 \(l = n + 1\) 时，我们先找到右侧路径的第二个轻节点，根据归纳假设知，以该节点为根节点的子树至少有 \(2^l - 1\) 个节点
  • 再找第一个轻节点，由轻节点的定义知，它的左子树节点数一定大于右子树节点数，而上面提到的子树位于它的右子树处，所以以第一个轻节点为根节点的子树至少有 \(2 \times (2^l - 1) + 1 = 2^{l + 1} - 1\) 个节点。那么整个堆的节点个数一定大于 \(2^{l + 1} - 1\)，得证

评论区