二项堆

概述

二项堆是一种可合并堆，由多个二项树组成，支持高效的合并操作。

二项树

二项树Bk的递归定义： - B0是单节点树 - Bk由两棵Bk-1连接而成，一棵的根作为另一棵的左孩子

B0:  ●

B1:  ●
      |
      ●

B2:  ●
     |
    ●→●
    |
    ●

B3:      ●
         |
       ●→●→●
       |  |
      ●  ●
      |
      ●

二项树性质

1. Bk有2^k个节点
2. Bk的高度为k
3. Bk深度d处有C(k,d)个节点
4. 根的度数为k

数据结构

typedef struct BinomialTreeNode {
    int value;
    int degree;
    struct BinomialTreeNode *parent;
    struct BinomialTreeNode *child;
    struct BinomialTreeNode *sibling;
} BinomialTreeNode;

typedef struct {
    BinomialTreeNode *head;
} BinomialHeap;

创建节点

BinomialTreeNode* createBinomialNode(int value) {
    BinomialTreeNode *node = (BinomialTreeNode*)malloc(sizeof(BinomialTreeNode));
    node->value = value;
    node->degree = 0;
    node->parent = NULL;
    node->child = NULL;
    node->sibling = NULL;
    return node;
}

BinomialHeap* createBinomialHeap() {
    BinomialHeap *heap = (BinomialHeap*)malloc(sizeof(BinomialHeap));
    heap->head = NULL;
    return heap;
}

合并两棵二项树

BinomialTreeNode* linkBinomialTrees(BinomialTreeNode *t1, BinomialTreeNode *t2) {
    if (t1->value > t2->value) {
        BinomialTreeNode *temp = t1;
        t1 = t2;
        t2 = temp;
    }
    
    t2->parent = t1;
    t2->sibling = t1->child;
    t1->child = t2;
    t1->degree++;
    
    return t1;
}

合并两个堆

BinomialHeap* mergeBinomialHeaps(BinomialHeap *h1, BinomialHeap *h2) {
    BinomialHeap *result = createBinomialHeap();
    
    BinomialTreeNode *curr1 = h1->head;
    BinomialTreeNode *curr2 = h2->head;
    BinomialTreeNode **tail = &result->head;
    
    while (curr1 && curr2) {
        if (curr1->degree <= curr2->degree) {
            *tail = curr1;
            curr1 = curr1->sibling;
        } else {
            *tail = curr2;
            curr2 = curr2->sibling;
        }
        tail = &((*tail)->sibling);
    }
    
    *tail = curr1 ? curr1 : curr2;
    
    return result;
}

BinomialHeap* unionBinomialHeaps(BinomialHeap *h1, BinomialHeap *h2) {
    BinomialHeap *heap = mergeBinomialHeaps(h1, h2);
    
    if (heap->head == NULL) return heap;
    
    BinomialTreeNode *prev = NULL;
    BinomialTreeNode *curr = heap->head;
    BinomialTreeNode *next = curr->sibling;
    
    while (next) {
        if (curr->degree != next->degree ||
            (next->sibling && next->sibling->degree == curr->degree)) {
            prev = curr;
            curr = next;
        } else {
            if (curr->value <= next->value) {
                curr->sibling = next->sibling;
                linkBinomialTrees(curr, next);
            } else {
                if (prev == NULL) {
                    heap->head = next;
                } else {
                    prev->sibling = next;
                }
                linkBinomialTrees(next, curr);
                curr = next;
            }
        }
        next = curr->sibling;
    }
    
    return heap;
}

插入操作

BinomialHeap* insertBinomialHeap(BinomialHeap *heap, int value) {
    BinomialHeap *temp = createBinomialHeap();
    temp->head = createBinomialNode(value);
    
    BinomialHeap *result = unionBinomialHeaps(heap, temp);
    
    free(temp);
    return result;
}

提取最小值

BinomialTreeNode* findMin(BinomialHeap *heap) {
    if (heap->head == NULL) return NULL;
    
    BinomialTreeNode *min = heap->head;
    BinomialTreeNode *curr = heap->head->sibling;
    
    while (curr) {
        if (curr->value < min->value) {
            min = curr;
        }
        curr = curr->sibling;
    }
    
    return min;
}

BinomialHeap* reverseList(BinomialTreeNode *node) {
    BinomialTreeNode *prev = NULL;
    BinomialTreeNode *curr = node;
    
    while (curr) {
        BinomialTreeNode *next = curr->sibling;
        curr->sibling = prev;
        curr->parent = NULL;
        prev = curr;
        curr = next;
    }
    
    BinomialHeap *heap = createBinomialHeap();
    heap->head = prev;
    return heap;
}

int extractMin(BinomialHeap **heap) {
    if ((*heap)->head == NULL) return -1;
    
    BinomialTreeNode *min = (*heap)->head;
    BinomialTreeNode *minPrev = NULL;
    BinomialTreeNode *curr = (*heap)->head->sibling;
    BinomialTreeNode *prev = (*heap)->head;
    
    while (curr) {
        if (curr->value < min->value) {
            min = curr;
            minPrev = prev;
        }
        prev = curr;
        curr = curr->sibling;
    }
    
    if (minPrev == NULL) {
        (*heap)->head = min->sibling;
    } else {
        minPrev->sibling = min->sibling;
    }
    
    BinomialHeap *childHeap = reverseList(min->child);
    *heap = unionBinomialHeaps(*heap, childHeap);
    
    int minValue = min->value;
    free(min);
    free(childHeap);
    
    return minValue;
}

时间复杂度

操作	时间复杂度
合并	O(log n)
插入	O(log n)
获取最小值	O(log n)
删除最小值	O(log n)
减少键值	O(log n)
删除	O(log n)

二项堆 vs 斐波那契堆

特性	二项堆	斐波那契堆
插入	O(log n)	O(1) 摊还
删除最小值	O(log n)	O(log n) 摊还
合并	O(log n)	O(1) 摊还
实现复杂度	中等	复杂

应用场景

1. 可合并优先队列：多队列管理
2. 图算法：Dijkstra、Prim优化
3. 事件模拟：多事件源合并
4. 分布式系统：分布式优先队列

参考资料

• 《算法导论》第19章
• 《数据结构与算法分析》第6章