左偏树是一种满足堆性质和左偏性质的二叉树结构，其核心操作合并的时间复杂度为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。
C++ 实现示例
下面是一个简洁的小根左偏树实现：
#include <iostream>
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);
}
}使用示例
测试代码：
```cpp int main() { LeftistNode* heap = nullptr; heap = insert(heap, 3); heap = insert(heap, 1); heap = insert(heap, 5); heap = insert(heap, 2);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;
}
<p>输出结果大致为：</p> <pre> Top: 1 New top: 2 Merged top: 0 </pre> <H3>时间复杂度分析</H3> <p>所有主要操作的时间复杂度均为 O(log n)：</p> <ul> <li>merge: O(log n)</li> <li>insert: O(log n)，相当于 merge 一个单节点堆</li> <li>pop: O(log n)，合并左右子树</li> <li>top: O(1)</li> </ul> <p>左偏树的优势在于合并效率高，适合动态合并多个优先队列的场景。</p> 基本上就这些。实现时注意指针安全和递归边界即可。
