二项堆

二项堆是Vuillemin发明，这种数据结构，能够有效支持插入，删除 混合 检索最小 等操作，优点是结构比较精致，而且比较简单。

闲言少叙，上代码。

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

#define MIN_KEY 0xFFFFFFFF
typedef struct __Bino_node{
    int key;
    int value;
    int degree;
    struct __Bino_node *parent;
    struct __Bino_node *child;
    struct __Bino_node *next;
} Bino_node;

typedef struct{
    Bino_node *head;
}Bino_heap;

int CreatBinomialHeap(Bino_heap *heap)
{
    (heap)->head = NULL;
    return 0;
}

int BinomialLink(Bino_node *root,Bino_node *y)
{
    y->parent = root;
    y->next = root->child;
    root->child = y;
    root->degree++;

    return 0;
}

int InitBinomialNode(Bino_node* node ,int key ,int value)
{
    if(node == NULL)
    {
        return -1;
    }

    node->key = key;
    node->value = value;
    node->degree = 0;
    node->parent = NULL;
    node->child = NULL;
    node->next = NULL;
    return 0;
}

Bino_node* BinomialHeapMerge(Bino_node* a,Bino_node* b)
{
    Bino_node *head = NULL;
    Bino_node **pos = &head;

    while(a && b)
    {
        if(a->degree < b->degree)
        {
            *pos = a;
            a = a->next;
        }
        else
        {
            *pos = b;
            b = b->next;
        }
        pos = &(*pos)->next;

    }

    if(a)
        *pos = a;
    else
        *pos = b;
    return head;

}
int BinomialHeapUnion(Bino_heap* heapx,Bino_heap* heapy)
{
    Bino_node *head = NULL;
    Bino_node *prev ,*cur,*next;
    if(heapx == NULL || heapy == NULL)
    {
        printf("at least one heap point is null\r\n");
        return -1;
    }

    head = BinomialHeapMerge(heapx->head,heapy->head);
    prev = NULL;
    cur = head;
    next = head->next;
    while(next)
    {
        if(cur->degree != next->degree ||
                (next->next)&&(next->degree == next->next->degree))
        {
            prev = cur;
            cur = next;
            next = cur->next;
        }
        else
        {
            if(cur->key <next->key)
            {
                cur->next = next->next;
                BinomialLink(cur,next);
                next = cur->next;
            }
            else
            {
                if(prev == NULL)
                    head = next;
                else
                    prev->next = next;
                BinomialLink(next,cur);
                cur = next;
                next = cur->next;
            }
        }
    }

    heapx->head = head;
    return 0;
}


int BinomialHeapInsertNode(Bino_heap* heap,Bino_node* node)
{
    Bino_heap heap2 = {0};
    int ret = -1;
    if(heap ==NULL || node == NULL)
    {
        printf("heap or node is null pointer\r\n");
        return -1;
    }

    ret = CreatBinomialHeap(&heap2);
    if(ret)
    {
        printf("create new heap failed \r\n");
        return -2;
    }

    heap2.head = node;

    BinomialHeapUnion(heap,&heap2);
    return 0;
}

Bino_node* BinomialReverse(Bino_node *node)
{
    Bino_node* tail = NULL;
    Bino_node* next;

    if(node == NULL)
    {
        return node;
    }

    node->parent = NULL;
    while(node->next)
    {
        next = node->next;
        node->next = tail;
        tail = node;
        node = next;
        node->parent = NULL;
    }

    node->next = tail;
    return node;

}

int ExtractBinomialHeapMin(Bino_heap *heap,Bino_node** min_node)
{
    Bino_node* prev = NULL;  /*prev is to find the node previous of the min node*/
    Bino_node* cur = heap->head;
    *min_node = heap->head;
    Bino_heap heap2;

    while(cur->next)
    {
        if((*min_node)->key > cur->next->key)
        {
            *min_node = cur->next;
            prev = cur;

        }
        cur = cur->next;
    }

    if(prev == NULL)
        heap->head = (*min_node)->next;
    else
        prev->next = (*min_node)->next;

    heap2.head = BinomialReverse((*min_node)->child);
    BinomialHeapUnion(heap,&heap2);
    return 0;
}

int BinomialHeapDecreaseKey(Bino_heap* heap,Bino_node *node,int newkey)
{
    Bino_node *parent = NULL;
    int tmp_key;
    int tmp_value;
    if(newkey > node->key)
    {
        printf("new key is big than old key,should exit\r\n");
        return -1;
    }

    node->key = newkey;
    parent = node->parent;

    while(parent && parent->key > node->key)
    {
        tmp_key = parent->key;
        tmp_value = parent->value;
        parent->key = node->key;
        parent->value = node->value;
        node->key = tmp_key;
        node->value = tmp_value;

        node = parent;
        parent = node->parent;
    }
    return 0;

}

int BinomialHeapDelete(Bino_heap* heap,Bino_node *node)
{
    Bino_node *min_node = NULL;
    BinomialHeapDecreaseKey(heap,node,MIN_KEY);
    ExtractBinomialHeapMin(heap,&min_node);
    return 0;
}

void test_del()
{

    Bino_heap heap = {0};
    Bino_node node1,node2,node3,node4,node5,node6;

    CreatBinomialHeap(&heap);

    InitBinomialNode(&node1,3,55);
    BinomialHeapInsertNode(&heap,&node1);

    InitBinomialNode(&node2,11,43);
    BinomialHeapInsertNode(&heap,&node2);

    InitBinomialNode(&node3,9,65);
    BinomialHeapInsertNode(&heap,&node3);

    InitBinomialNode(&node4,7,78);
    BinomialHeapInsertNode(&heap,&node4);

    InitBinomialNode(&node5,15,44);
    BinomialHeapInsertNode(&heap,&node5);

    BinomialHeapDelete(&heap,&node4);
    assert(heap.head->key == 3);
    assert(heap.head->child->next->key == 9);
    assert(heap.head->child->child->key == 15);

}
void test_BinomialHeapDecreaseKey()
{

}
void test_ExtractBinomialHeapMin()
{

    Bino_heap heap = {0};
    Bino_node node1,node2,node3,node4,node5,node6;

    CreatBinomialHeap(&heap);

    InitBinomialNode(&node1,rand(),rand());
    BinomialHeapInsertNode(&heap,&node1);

    InitBinomialNode(&node2,rand(),rand());
    BinomialHeapInsertNode(&heap,&node2);

    InitBinomialNode(&node3,rand(),rand());
    BinomialHeapInsertNode(&heap,&node3);

    InitBinomialNode(&node4,rand(),rand());
    BinomialHeapInsertNode(&heap,&node4);

    InitBinomialNode(&node5,rand(),rand());
    BinomialHeapInsertNode(&heap,&node5);

    InitBinomialNode(&node6,17,78);
    BinomialHeapInsertNode(&heap,&node6);

    Bino_node *min_node;
    ExtractBinomialHeapMin(&heap,&min_node);
    printf("min_node Key is %d\r\n",min_node->key);

}
void test_BinomialHeapInsertNode()
{
    Bino_heap heap = {0};
    Bino_node node1,node2,node3,node4,node5,node6;

    CreatBinomialHeap(&heap);

    InitBinomialNode(&node1,3,55);
    BinomialHeapInsertNode(&heap,&node1);

    InitBinomialNode(&node2,11,43);
    BinomialHeapInsertNode(&heap,&node2);

    InitBinomialNode(&node3,9,65);
    BinomialHeapInsertNode(&heap,&node3);

    InitBinomialNode(&node4,7,78);
    BinomialHeapInsertNode(&heap,&node4);

    InitBinomialNode(&node5,15,44);
    BinomialHeapInsertNode(&heap,&node5);

    Bino_node* head = heap.head;
    printf("head->key = %d,head->next->key : %d\r\n",head->key,head->next->key);


}
void test_BinomialHeapMerge()
{
    Bino_node a ={0};
    Bino_node b = {0};
    Bino_node *head = NULL;
    InitBinomialNode(&a,6 ,66);
    InitBinomialNode(&b,7,777);
    head = BinomialHeapMerge(&a,&b);
    printf("head->key:%d\thead->value :%d\r\n",head->key,head->value);
    printf("head->next->key :%d\thead->next->value :%d\r\n",head->next->key,head->next->value);

}
void test_FineBinomialHeapMin()
{

}
void test_CreatBinomialHeap()
{
    Bino_heap heap = {0};
    int ret;
    ret =    CreatBinomialHeap(&heap);
    if(ret == 0)
    {
        printf("the address of heap is %ld \r\n",(long)heap.head);
    }

}
void test_Bino_heap()
{
    Bino_heap heap;
}
void test_Bino_node()
{
    Bino_node node;
}
int test()
{
    //test_Bino_node();
    //test_Bino_heap();
    //test_CreatBinomialHeap();
    //test_BinomialHeapMerge();
    //test_BinomialHeapInsertNode();
    //test_BinomialReverse();
    //test_ExtractBinomialHeapMin();
    test_del();

}
int main()
{
    test();
    return 0;
}