斐波那契堆的实现

//斐波那契堆的介绍参考<<数据结构>>Ellis Horowitz等著，李建中等译P294

/*
 * 2008/07/10 By YaoJianming
 * */
#include
#include
#include

struct element {
        int key;
};
struct fiboheap {
        element data;
        fiboheap *child;
        fiboheap *left_link;
        fiboheap *right_link;
        int degree;
        bool child_cut;
        fiboheap *parent;
};
#define TREELEN 8

void join_min_trees(fiboheap *&a, fiboheap *b)
{
        if(a->data.key < b->data.key) {
                if(a->child == NULL) {
                        a->right_link = a->left_link = a;
                        b->right_link = b->left_link = b;
                } else {
                        fiboheap *temp = a->child->left_link;
                        a->child->left_link = b;
                        b->right_link = a->child;
                        b->left_link = temp;
                        temp->right_link = b;
                }
                a->child = b;
                a->degree++;
                b->parent = a;
                b->child_cut = true;
        } else {
                if(b->child == NULL) {
                        a->right_link = a->left_link = a;
                        b->right_link = b->left_link = b;
                } else {
                        fiboheap *temp = b->child->left_link;
                        b->child->left_link = a;
                        a->right_link = b->child;
                        a->left_link = temp;
                        temp->right_link = a;
                }
                b->child = a;
                b->degree++;
                a->parent = b;
                a->child_cut = true;
                a = b;
        }
}

//寻找于所给值相同的节点

fiboheap *find(fiboheap *a, int key)
{
        fiboheap *p = a;
        do {
                if(p->data.key == key) {
                        return p;
                }
                if (p->child != NULL) {
                        fiboheap *q = find(p->child, key);
                        if(q != NULL) return q;
                }
                p = p->right_link;
        } while(p != a);
        return NULL;
}

element del_min(fiboheap*&);
//删除与所给值相同的节点

void del_fix(fiboheap *&a, int key)
{
        fiboheap *p = find(a, key);
        if(p == NULL) {//堆中没有与所给值相同的节点

            return;

        } else if(p == a) {//正好要删除最小值
                del_min(p);
        } else if(p->child_cut == false) {//删除处于顶点节点所组成的双向循环链表中
                fiboheap *i = p->left_link;
                fiboheap *j = p->right_link;
                fiboheap *k = p->child;
                fiboheap *m = k->left_link;
                i->right_link = k;
                k->left_link = i;
                m->right_link = j;
                j->left_link = m;
                k->parent = NULL;
                k->child_cut = false;
                free(p);
        } else {//删除不在由顶点节点所组成的双向循环链表中
                if(p->degree == 0) {//节点下面没有子节点了
                        p->parent->child = NULL;
                        p->parent->degree--;
                } else {//节点下面还有子节点
                        fiboheap *p_left = p->left_link;
                        fiboheap *p_right = p->right_link;
                        p_left->right_link = p_right;
                        p_right->left_link = p_left;
                        p->parent->child = p_right;
                        p->parent->degree--;

                        fiboheap *child = p->child;
                        child->parent = NULL;
                        child->child_cut = false;
                        fiboheap *child_left = child->left_link;
                        fiboheap *a_right = a->right_link;
                        a->right_link = child;
                        child->left_link = a;
                        child_left->right_link = a_right;
                        a_right->left_link = child_left;
                }

                //级联剪枝操作  

                fiboheap *del_node = p;
                p = p->parent;
                while(p->child_cut != false) {
                        fiboheap *parent = p->parent;
                        p->parent = NULL;
                        fiboheap *p_left = p->left_link;
                        fiboheap *p_right = p->right_link;
                        p_left->right_link = p_right;
                        p_right->left_link = p_left;
                        p->child_cut = false;
                        parent->child = p_right;
                        parent->degree--;

                        fiboheap *a_right = a->right_link;
                        a->right_link = p;
                        p->right_link = a_right;
                        p->left_link = a;
                        a_right->left_link = p;
                        p = parent;
                }
                free(del_node);
        }
}

//关键值减值操作

void decrease(fiboheap *&a, int key, int value)
{
        fiboheap *p = find(a, key);
        if(p == a) {//无对应的节点
                p->data.key -= value;
        } else if(p->child == false) {//所操作节点处于顶点节点组成的双向循环链表中
                p->data.key -= value;
                if(p->data.key < a->data.key) {
                        a = p;
                }
        } else {
                fiboheap *q = p;
                p->data.key -= value;
                //级联剪枝操作

                while(p->child_cut != false) {
                        fiboheap *parent = p->parent;
                        p->parent = NULL;
                        fiboheap *p_left = p->left_link;
                        fiboheap *p_right = p->right_link;
                        p_left->right_link = p_right;
                        p_right->left_link = p_left;
                        p->child_cut = false;
                        parent->child = p_right;
                        parent->degree--;

                        fiboheap *a_right = a->right_link;
                        a->right_link = p;
                        p->right_link = a_right;
                        p->left_link = a;
                        a_right->left_link = p;
                        p = parent;
                }
                if(q->data.key < a->data.key) {
                        a = q;
                }
        }
}

element del_min(fiboheap *&a)
{
        element temp = a->data;
        fiboheap *tree[TREELEN];
        for(int i=0; i                tree[i] = NULL;
        }

        fiboheap *p1, *p2;
        if(a->left_link != a) {
                p1 = a->left_link;
                p1->right_link = a->right_link;
                a->right_link->left_link = p1;
        }
        p2 = a->child;
        fiboheap *m1 = p1;
        fiboheap *m2 = p2;
        do {
                if(m1 == NULL) break;
//              printf("%d\n", m1->data.key);
                int degree;
                fiboheap *w = m1->right_link;
                for(degree=m1->degree; tree[degree]; ++degree) {
                        join_min_trees(m1, tree[degree]);
                        tree[degree] = NULL;
                }
                tree[degree] = m1;
                m1 = w;
        } while (m1 != p1);
        do {
                if(m2 == NULL) break;
//              printf("%d\n", m2->data.key);
                int degree;
                fiboheap *w = m2->right_link;
                for(degree=m2->degree; tree[degree]; ++degree) {
                        join_min_trees(m2, tree[degree]);
                        tree[degree] = NULL;
                }
                tree[degree] = m2;
                m2 = w;
        } while (m2 != p2);

        int k = 0;
        for(int i=0; i                if(tree[i] == NULL) continue;
                k++;
                if(k == 1) {
                        tree[i]->right_link = tree[i]->left_link = tree[i];
                        a = tree[i];
                } else if(k > 1) {
                        fiboheap *temp = a->right_link;
                        a->right_link = tree[i];
                        temp->left_link = tree[i];
                        tree[i]->right_link = temp;
                        tree[i]->left_link = a;
                        if(a->data.key > tree[i]->data.key) a = tree[i];
                }
        }
        return temp;
}

void insert(fiboheap *&a, fiboheap *b)
{
        if(a == NULL) {
                a = b;
                return;
        }
        fiboheap *temp = a->right_link;
        a->right_link = b;
        b->right_link = temp;
        temp->left_link = b;
        b->left_link = a;
        if(a->data.key > b->data.key) {
                a = b;
        }
}

void merge(fiboheap *&a, fiboheap *b)
{
        if(a == NULL) {
                a = b;
                return;
        }
        fiboheap *p1 = a->right_link;
        fiboheap *p2 = b->left_link;
        a->right_link = b;
        b->left_link = a;
        p1->left_link = p2;
        p2->right_link = p1;
        if(a->data.key > b->data.key) {
                a = b;
        }
}

void traverse(fiboheap *a)
{
        fiboheap *p = a;
        do {
                printf("%4d%4d%4d", p->data.key, p->degree, p->child_cut);
                if(p->child != NULL) printf(" 1 ");
                else printf(" 0 ");
                if(p->parent != NULL) printf(" 1 ");
                else printf(" 0 ");
                printf("\n");
                if (p->child != NULL) {
                        traverse(p->child);
                }
                p = p->right_link;
        } while(p != a);
}

int main()
{
        fiboheap *a = NULL;
        for(int i=1; i<=8; ++i) {
                fiboheap *p = new fiboheap;
                p->right_link = p->left_link = p;
                p->child = p->parent = NULL;
                p->data.key = i;
                p->degree = 0;
                p->child_cut = false;
                insert(a, p);
        }
        fiboheap *b = NULL;
        for(int i=9; i<=17; ++i) {
                fiboheap *p = new fiboheap;
                p->right_link = p->left_link = p;
                p->child = p->parent = NULL;
                p->data.key = i;
                p->degree = 0;
                p->child_cut = false;
                insert(b, p);
        }
        del_min(a);
        del_min(b);
        merge(a, b);
        traverse(a);
        printf("\n");
        decrease(a, 13, 15);
//      del_fix(a, 13);
        traverse(a);
}