二项堆（c语言）完整代码

二项堆（Binomial Heap）是一种非常高效的数据结构，它可以在插入、删除和合并等操作上达到O(logn)的时间复杂度。下面是二项堆的C语言实现代码：

#include <stdio.h>
#include <stdlib.h>

// 二项堆节点结构体
typedef struct node {
    int val;                // 节点的值
    int degree;             // 节点的度数
    struct node *child;     // 节点的左孩子
    struct node *sibling;   // 节点的右兄弟
} Node;

// 创建节点
Node *create_node(int val) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->val = val;
    node->degree = 0;
    node->child = NULL;
    node->sibling = NULL;
    return node;
}

// 合并两个二项堆
Node *merge(Node *h1, Node *h2) {
    if (h1 == NULL) {
        return h2;
    }
    if (h2 == NULL) {
        return h1;
    }
    Node *head = NULL;      // 合并后的堆的头节点
    Node *tail = NULL;      // 合并后的堆的尾节点
    Node *p1 = h1;
    Node *p2 = h2;
    while (p1 != NULL && p2 != NULL) {
        if (p1->degree <= p2->degree) {
            if (head == NULL) {
                head = p1;
            } else {
                tail->sibling = p1;
            }
            tail = p1;
            p1 = p1->sibling;
        } else {
            if (head == NULL) {
                head = p2;
            } else {
                tail->sibling = p2;
            }
            tail = p2;
            p2 = p2->sibling;
        }
    }
    if (p1 != NULL) {
        tail->sibling = p1;
    } else {
        tail->sibling = p2;
    }
    return head;
}

// 插入节点
Node *insert(Node *h, int val) {
    Node *node = create_node(val);
    return merge(h, node);
}

// 查找最小值节点
Node *find_min(Node *h) {
    Node *min_node = h;
    Node *p = h->sibling;
    while (p != NULL) {
        if (p->val < min_node->val) {
            min_node = p;
        }
        p = p->sibling;
    }
    return min_node;
}

// 删除最小值节点
Node *delete_min(Node *h) {
    Node *min_node = find_min(h);
    if (min_node == h) {    // 头节点就是最小值节点
        h = h->sibling;
    } else {                // 删除最小值节点，然后将其子树与其他树合并
        Node *pre_min_node = h;
        while (pre_min_node->sibling != min_node) {
            pre_min_node = pre_min_node->sibling;
        }
        pre_min_node->sibling = min_node->sibling;
        Node *child_h = min_node->child;      // 将最小值节点的子树反转后插入到堆中
        Node *new_h = NULL;
        while (child_h != NULL) {
            Node *next_child_h = child_h->sibling;
            child_h->sibling = new_h;
            new_h = child_h;
            child_h = next_child_h;
        }
        h = merge(h, new_h);
        free(min_node);
    }
    return h;
}

int main() {
    Node *h = NULL;         // 二项堆
    int n, op, val;
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &op);
        switch (op) {
            case 0:     // 插入节点
                scanf("%d", &val);
                h = insert(h, val);
                break;
            case 1:     // 查找最小值节点
                printf("%d\n", find_min(h)->val);
                break;
            case 2:     // 删除最小值节点
                h = delete_min(h);
                break;
        }
    }
    return 0;
}