二项树

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

struct node {
        int key;
        int degree;
        struct node *child;
        struct node *prev;
        struct node *next;
};

void init_node (struct node *node, int key)
{
        node->key = key;
        node->degree = 0;
        node->child = NULL;
        node->prev = node;
        node->next = node;
}
struct node *merge(struct node *t1, struct node *t2)
{
        if (!t1)
                return t2;
        if (!t2)
                return t1;

        struct node *tail = NULL;
        tail = t1->prev;
        t2->prev->next = t1;
        t1->prev = t2->prev;

        t2->prev = tail;
        tail->next = t2;

        if (t1->key < t2->key)
                return t1;
        else
                return t2;
}
void insert(struct node **tree, int key)
{
        struct node *now = malloc(sizeof(struct node));
        assert(now);
        init_node(now, key);
        *tree = merge(*tree, now);
}
struct node *join(struct node *t1, struct node *t2)
{
        if (!t1)
                return t2;
        if (!t2)
                return t1;
        if (t1->key > t2->key) {
                struct node *tmp = t1;
                t1 = t2;
                t2 = tmp;
        }

        t1->degree ++;
        struct node *child = t1->child;
        if (!child) {
                t2->prev = t2->next = t2;
                t1->child = t2;
        } else {
                struct node *next = child->next;
                child->next = t2;
                t2->prev = child;
                t2->next = next;
                next->prev = t2;
        }
        return t1;
}
struct node *adjust(struct node *node)
{
        if (node == NULL)
                return NULL;

        struct node *arr[32] = {NULL};
        struct node *head = node;
        do {
                struct node *tmp = head;
                head = head->next;
                int degree = tmp->degree;
                while (arr[degree] != NULL) {
                        tmp = join(tmp, arr[degree]);
                        arr[degree] = NULL;
                        degree ++;
                }
                arr[degree] = tmp;
        } while (head != node);
int min = INT_MAX;
        struct node *ret = NULL;

        head = NULL;
        for (int i = 0; i<32; i++) {
                if (arr[i]) {
                        if (arr[i]->key < min) {
                                ret = arr[i];
                                min = ret->key;
                        }
                        if (head == NULL) {
                                head = arr[i];
                                head->next = head;
                                head->prev = head;
                        } else {
                                struct node *next = head->next;

                                head->next = arr[i];
                                arr[i]->prev = head;
                                arr[i]->next = next;
                                next->prev = arr[i];
                        }
                }
        }

        return ret;
}
int delmin(struct node **tree)
{
        if (*tree == NULL) {
                fprintf(stderr, "the tree is empty");
                exit(1);
        }
        struct node *tmp = *tree;
        struct node *child = tmp->child;
        struct node *next = NULL;
        int ret = tmp->key;
        if (tmp->next == tmp) {
                next = NULL;
        } else {
                tmp->prev->next = tmp->next;
                tmp->next->prev = tmp->prev;
                next = tmp->next;

        }
        free (tmp);
         //这里并不需要child和next是各个链表中是最小的
        tmp = merge(child, next);
        *tree = adjust(tmp);
        return ret;
}