左式堆与斜堆

左式堆(Leftist heap)

定义

直观理解

&emsp；我们从左式堆的定义开始。顾名思义，左式堆就是“左偏”的堆，为了明确“左偏”的定义，我们给出一个定义零路径长。

零路径长(null path length, NPL)

我们把任一节点X的零路径长Npl(X)定义为从X到一个没有两个子节点的的最短路径的长(本质是寻找到空节点的距离)。因此，具有1或0个子节点的节点的Npl为0。另外规定$Npl(NULL)=\textit{-1}$
由这个定义可以知道每个节点的Npl就等于它子节点Npl中的较小值+1

左式堆的结构性质

左式堆的结构性质：每个结点的左孩子的Npl都要大于等于其右孩子的Npl
从这一性质可以引出另一个定理：在右路径上有$r$个节点的左式堆必然有至少$2^r-1$个节点（最小值的情况即完全二叉树）

左式堆的操作和实现

左式堆的操作介绍

左式堆有三个核心操作：
- Merge
- Insert
- Delte
其中Insert可以视为与一个独立节点的Merge，因此可以规约到Merge；而Delte的操作方式是删去根节点，然后对左右子树Merge，因此关键问题还是Merge

左式堆的归并(Merge)

递归实现

操作逻辑

如果两个堆中有一个是空的，那么直接返回另一个
如果两个堆都非空，我们比较两个堆的根节点key的大小，key小的是H1，大的是H2；
如果H1只有一个根节点，将H2连接到H1的左子树（实际可以被包含在下面的操作中）
如果H1不只有根节点，则将H1的右子树与H2合并
如果H1的Npl属性被违反，则交换两个子树
更新H1的Npl

示例代码

 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
26
27


inline int Npl(Heap* x)
{
    return x ? x->Npl : -1;
}

Heap* Merge(Heap* H1, Heap* H2)
{
    if(H2 == NULL) 
        return H1;
    if(H1 == NULL)
        return H2;
    //处理存在空堆的情况

    if(H1->val > H2->val) 
        swap(H1, H2);
    //正确地选择H1

    H1->right = Merge(H1->right, H2);
    if(Npl(H1->left) < Npl(H1->right)) 
    {
        swap(H1->left, H1->right);
    }
    // 递归归并
    H1->Npl = Npl(H1->right)+1;
    //更新Npl
    return H1;
}

迭代实现

操作逻辑

如果有一个堆是空的，那么直接返回另一个堆
如果两个堆都非空，比较根节点的键值大小，选取小的作为H1
创建分别指向两个根节点的指针a和b
当a和b都非空时，比较a和b的键值，如果a的键值大于b，交换a和b
将a节点压入栈
a移动到a的右子节点
重复以上3步直到有a或b为NULL（有一个堆被全部遍历）
将剩余的非空一侧作为尾部
从栈中弹出节点p
使用p在tail上自下向上搭建堆
更新Npl
更新tail
重复以上4步直到栈为空

示例代码

 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
26
27
28
29
30
31
32
33
34
35
36
37


inline int Npl(Heap* x)
{
    return x ? x->Npl : -1;
}

Heap* Merge(Heap* H1, Heap* H2)
{
    if(!H1)
        return H2;
    if(!H2)
        return H1;
    
    Heap *a = H1, *b = H2;
    vector<Heap*> stk;
    while (a && b)
    {
        if(a->val > b->val)
            swap(a, b);
            stk.push_back(a);
            a = a->right;
    }

    Heap* tail = a ? a : b;

    while(!stk.empty())
    {
        Heap* p = stk.back();
        stk.pop_back();
        p->right = tail;
        if(Npl(p->left) < Npl(p->right))
            swap(p->left, p->right);
        p->Npl = Npl(p->right) + 1;
        tail = p;
    }

    return tail;
}

斜堆(Skew Heap)

斜堆与左式堆的关系

斜堆与左式堆都是自调整的可合并优先队列，所有操作都基于合并，且合并总是沿着右路径进行
斜堆不需要维护Npl等信息，唯一的自调整策略为在每次合并的回溯阶段无条件交换当前根的左右子树。这样使得树形态不断自适应，避免长期偏斜。
斜堆不保证严格的对数深度，但能够证明合并的摊还时间为$O(log n)$，实践中常比左式堆常数更小、实现更简洁。

合并操作

递归合并

操作逻辑

若一方为空，直接返回另一方
若双方都不为空，比较根节点键值，键值较小的作为H1，键值较大的作为H2
归并H1的右子树与H2
交换H1的左右子树
返回H1

示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


inline int Npl(Heap* x)
{
    return x ? x->Npl : -1;
}

Heap* Merge(Heap* H1, Heap* H2)
{
    if(!H1)
        return H2;
    if(!H2)
        return H1;
    
    if(H1->key > H2->key) 
        swap(H1, H2);
    a->right = merge(H1->right, H2);
    
    swap(H1->left, H1->right);
    return a;
}

迭代归并

 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
26


Heap* Merge(Heap* H1, Heap* H2) {
    if (!H1) return H2;
    if (!H2) return H1;

    Heap *a = H1, *b = H2;
    vector<Heap*> S;

    // 向下：总让较小根为 a，只沿 a->right 前进，并把路径入栈
    while (a && b) {
        if (a->val > b->val) swap(a, b);
        S.push_back(a);
        a = a->right;
    }

    // 剩余非空一侧作为尾部
    Heap* tail = a ? a : b;

    // 回溯：连接右子并无条件交换左右子
    while (!S.empty()) {
        Heap* p = S.back(); S.pop_back();
        p->right = tail;
        swap(p->left, p->right);  // 斜堆特性：无条件交换
        tail = p;
    }
    return tail;
}