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

#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);
    }
}

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>

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