C++怎么实现一个左偏树_C++可合并堆(Mergeable Heap)的高效数据结构

左偏树是一种满足堆性质和左偏性质的二叉树结构，其核心操作合并的时间复杂度为O(log n)，插入、删除等操作均基于合并实现，适用于频繁合并堆的场景。

左偏树（Leftist Tree），又称左偏堆，是一种可合并堆（Mergeable Heap），支持高效地合并两个堆，相比二叉堆在合并操作上更优。它常用于需要频繁合并堆的场景，比如优先队列的合并、Dijkstra算法的优化版本等。

什么是左偏树？

左偏树是一种二叉树结构的堆，满足以下两个性质：

• 堆性质：父节点的值小于等于（小根堆）或大于等于（大根堆）子节点的值。
• 左偏性质：每个节点的左子树的“距离”（最短路径到空节点的长度，称为s-value或npl）不小于右子树的距离。

这个左偏性质保证了树向左“偏”，从而使得合并操作的时间复杂度为 O(log n)。

核心操作：合并（Merge）

合并是左偏树的核心操作，其他操作如插入、删除都可以基于合并实现。

立即学习“C++免费学习笔记（深入）”；

合并两个左偏树的基本思路如下：

• 假设我们维护的是小根堆，比较两棵树的根节点，取较小者作为新根。
• 将较小根的右子树与另一棵树递归合并。
• 合并完成后，检查左偏性质：若左子树的 s-value 小于右子树，则交换左右子树。
• 更新当前节点的 s-value：s-value = 右子树的 s-value + 1。

注意：空节点的 s-value 定义为 0，非空叶节点的 s-value 为 1。

AI at Meta

Facebook 旗下的AI研究平台

下载

C++ 实现示例

下面是一个简洁的小根左偏树实现：

#include 
using namespace std;

struct LeftistNode {
    int val;
    int dist;  // s-value: shortest path to a null node
    LeftistNode* left;
    LeftistNode* right;

    explicit LeftistNode(int v) : val(v), dist(0), left(nullptr), right(nullptr) {}
};

// 合并两个左偏树，返回新的根节点
LeftistNode* merge(LeftistNode* a, LeftistNode* b) {
    if (!a) return b;
    if (!b) return a;

    // 维护小根堆：a 的值必须 <= b 的值
    if (a->val > b->val) swap(a, b);

    // 递归合并 a 的右子树和 b
    a->right = merge(a->right, b);

    // 维护左偏性质
    if (!a->left || (a->right && a->left->dist < a->right->dist)) {
        swap(a->left, a->right);
    }

    // 更新距离
    a->dist = (a->right ? a->right->dist : 0) + 1;

    return a;
}

// 插入一个值
LeftistNode* insert(LeftistNode* root, int val) {
    return merge(root, new LeftistNode(val));
}

// 删除最小值（根节点）
LeftistNode* pop(LeftistNode* root) {
    if (!root) return nullptr;
    LeftistNode* left = root->left;
    LeftistNode* right = root->right;
    delete root;
    return merge(left, right);
}

// 获取最小值
int top(LeftistNode* root) {
    return root ? root->val : -1; // 假设所有值为正
}

// 中序遍历用于调试（非必要）
void inorder(LeftistNode* root) {
    if (root) {
        inorder(root->left);
        cout << root->val << "(dist=" << root->dist << ") ";
        inorder(root->right);
    }
}

使用示例

测试代码：

cout << "Top: " << top(heap) << endl; // 输出 1

heap = pop(heap);
cout << "New top: " << top(heap) << endl; // 输出 2

// 合并另一个堆
LeftistNode* heap2 = nullptr;
heap2 = insert(heap2, 4);
heap2 = insert(heap2, 0);
heap = merge(heap, heap2);

cout << "Merged top: " << top(heap) << endl; // 输出 0

return 0;

}

输出结果大致为：
Top: 1
New top: 2
Merged top: 0


时间复杂度分析
所有主要操作的时间复杂度均为 O(log n)：

merge: O(log n)
  
insert: O(log n)，相当于 merge 一个单节点堆
  
pop: O(log n)，合并左右子树
  
top: O(1)

左偏树的优势在于合并效率高，适合动态合并多个优先队列的场景。

基本上就这些。实现时注意指针安全和递归边界即可。