左堆（左式堆）¶

概述¶

左堆是一种可合并堆，支持高效合并两个堆的操作，通过零路径长维持平衡。

左堆性质¶

堆序性质：父节点优先级高于子节点
左偏性质：左子树零路径长 ≥ 右子树零路径长
零路径长：到最近外节点的距离

零路径长（NPL）¶

C
typedef struct LeftHeapNode {
    int value;
    int npl;
    struct LeftHeapNode *left;
    struct LeftHeapNode *right;
} LeftHeapNode;

int getNPL(LeftHeapNode *node) {
    if (node == NULL) return -1;
    return node->npl;
}

LeftHeapNode* createLeftHeapNode(int value) {
    LeftHeapNode *node = (LeftHeapNode*)malloc(sizeof(LeftHeapNode));
    node->value = value;
    node->npl = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

合并操作¶

C
LeftHeapNode* mergeLeftHeap(LeftHeapNode *h1, LeftHeapNode *h2) {
    if (h1 == NULL) return h2;
    if (h2 == NULL) return h1;
    
    if (h1->value > h2->value) {
        LeftHeapNode *temp = h1;
        h1 = h2;
        h2 = temp;
    }
    
    h1->right = mergeLeftHeap(h1->right, h2);
    
    if (getNPL(h1->left) < getNPL(h1->right)) {
        LeftHeapNode *temp = h1->left;
        h1->left = h1->right;
        h1->right = temp;
    }
    
    h1->npl = getNPL(h1->right) + 1;
    
    return h1;
}

插入操作¶

C
LeftHeapNode* insertLeftHeap(LeftHeapNode *heap, int value) {
    LeftHeapNode *node = createLeftHeapNode(value);
    return mergeLeftHeap(heap, node);
}

删除最小值¶

C
LeftHeapNode* deleteMinLeftHeap(LeftHeapNode *heap, int *minValue) {
    if (heap == NULL) {
        *minValue = -1;
        return NULL;
    }
    
    *minValue = heap->value;
    
    LeftHeapNode *left = heap->left;
    LeftHeapNode *right = heap->right;
    
    free(heap);
    
    return mergeLeftHeap(left, right);
}

获取最小值¶

C
int getMinLeftHeap(LeftHeapNode *heap) {
    if (heap == NULL) return -1;
    return heap->value;
}

C++ 实现¶

C++
class LeftHeap {
private:
    struct Node {
        int value;
        int npl;
        Node *left, *right;
        Node(int v) : value(v), npl(0), left(nullptr), right(nullptr) {}
    };
    
    Node *root;
    
    int getNPL(Node *node) {
        return node ? node->npl : -1;
    }
    
    Node* merge(Node *h1, Node *h2) {
        if (!h1) return h2;
        if (!h2) return h1;
        
        if (h1->value > h2->value) std::swap(h1, h2);
        
        h1->right = merge(h1->right, h2);
        
        if (getNPL(h1->left) < getNPL(h1->right)) {
            std::swap(h1->left, h1->right);
        }
        
        h1->npl = getNPL(h1->right) + 1;
        return h1;
    }
    
public:
    LeftHeap() : root(nullptr) {}
    
    void insert(int value) {
        Node *node = new Node(value);
        root = merge(root, node);
    }
    
    int getMin() {
        return root ? root->value : -1;
    }
    
    int extractMin() {
        if (!root) return -1;
        
        int minVal = root->value;
        Node *left = root->left;
        Node *right = root->right;
        
        delete root;
        root = merge(left, right);
        
        return minVal;
    }
    
    void mergeWith(LeftHeap &other) {
        root = merge(root, other.root);
        other.root = nullptr;
    }
};

斜堆¶

斜堆是左堆的简化版本，不维护NPL，每次合并后无条件交换左右子树。

C
typedef struct SkewHeapNode {
    int value;
    struct SkewHeapNode *left;
    struct SkewHeapNode *right;
} SkewHeapNode;

SkewHeapNode* mergeSkewHeap(SkewHeapNode *h1, SkewHeapNode *h2) {
    if (h1 == NULL) return h2;
    if (h2 == NULL) return h1;
    
    if (h1->value > h2->value) {
        SkewHeapNode *temp = h1;
        h1 = h2;
        h2 = temp;
    }
    
    SkewHeapNode *temp = h1->left;
    h1->left = mergeSkewHeap(h1->right, h2);
    h1->right = temp;
    
    return h1;
}

时间复杂度¶

操作	左堆	斜堆
合并	O(log n)	O(log n) 摊还
插入	O(log n)	O(log n) 摊还
删除最值	O(log n)	O(log n) 摊还
获取最值	O(1)	O(1)

左堆 vs 二叉堆¶

特性	左堆	二叉堆
合并效率	O(log n)	O(n)
空间效率	需要指针	数组紧凑
实现复杂度	较复杂	简单
适用场景	频繁合并	一般场景

应用场景¶

可合并堆：需要合并多个堆
优先队列合并：多队列归并
图算法：某些最短路径变种
事件模拟：多事件队列

参考资料¶

《数据结构与算法分析》第6章
《算法导论》堆相关章节