左偏树是一种满足堆性质和左偏性质的二叉树结构，其核心操作合并的时间复杂度为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 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 的值必须 val > b->val) swap(a, b); // 递归合并 a 的右子树和 b a->right = merge(a->right, b); // 维护左偏性质 if (!a->left || (a->right && a->left->dist 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 <val << "(dist=" <dist <right); }}
使用示例
测试代码：
“`cppint 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; // 输出 1heap = 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; // 输出 0return 0;
}
输出结果大致为：
Top: 1New top: 2Merged top: 0
时间复杂度分析
所有主要操作的时间复杂度均为 O(log n)：
merge: O(log n) insert: O(log n)，相当于 merge 一个单节点堆 pop: O(log n)，合并左右子树 top: O(1)
左偏树的优势在于合并效率高，适合动态合并多个优先队列的场景。
基本上就这些。实现时注意指针安全和递归边界即可。
以上就是C++怎么实现一个左偏树_C++可合并堆(Mergeable Heap)的高效数据结构的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485424.html
微信扫一扫 
支付宝扫一扫 
