斐波那契堆

C

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

typedef int Type;

typedef struct FibNode { 
    Type key;                        //关键字(键值)
    int degree;                      //度数
    struct FibNode *left;            //左兄弟
    struct FibNode *right;           //右兄弟
    struct FibNode *child;           //第一个孩子结点
    struct FibNode *parent;          //父结点
    int marked;                      //是否被删除第1个孩子(1表示删除，0表示未删除)
}FibNode;

typedef struct FibHeap {
    int   keyNum;                     //堆中结点的总数
    int   maxDegree;                  //最大度
    struct FibNode *min;              //最小结点(某个最小堆的根结点)
    struct FibNode **cons;            //最大度的内存区域
}FibHeap;

//将node从双链表移除
void fibNodeRemove(FibNode *node) {
    node->left->right = node->right;
    node->right->left = node->left;
}

//将单个结点node加入双向链表root之前
void fibNodeAdd(FibNode *node, FibNode *root) {
    node->left = root->left;
    root->left->right = node;
    node->right = root;
    root->left = node;
}

//将双向链表b链接到双向链表a的后面
void fibNodeCat(FibNode *a, FibNode *b) {
    FibNode *tmp;
    tmp = a->right;
    a->right = b->right;
    b->right->left = a;
    b->right = tmp;
    tmp->left = b;
}

//创建斐波那契堆
FibHeap* fibHeapMake() {
    FibHeap *heap;
    heap = (FibHeap *) malloc(sizeof(FibHeap));
    if (heap == NULL) {
        printf("Error: make FibHeap failed\n");
        return NULL;
    }
    heap->keyNum = 0;
    heap->maxDegree = 0;
    heap->min = NULL;
    heap->cons = NULL;
    return heap;
}

//创建斐波那契堆的结点
FibNode* fibNodeMake(Type key) {
    FibNode * node;
    node = (FibNode *) malloc(sizeof(FibNode));
    if (node == NULL) {
        printf("Error: make Node failed\n");
        return NULL;
    }
    node->key = key;
    node->degree = 0;
    node->left = node;
    node->right = node;
    node->parent = NULL;
    node->child = NULL;
    node->marked=0; 
    return node;
}

//将结点node插入到斐波那契堆heap中
void fibHeapInsert_node(FibHeap *heap, FibNode *node) {
    if (heap->keyNum == 0) {
        heap->min = node;
    }
    else {
        fibNodeAdd(node, heap->min);
        if (node->key < heap->min->key) {
            heap->min = node;
        }       
    }
    heap->keyNum++;
}

//新建键值为key的结点，并将其插入到斐波那契堆中
void fibHeapInsert_key(FibHeap *heap, Type key) {
    FibNode *node;
    if (heap == NULL) {
        printf("The heap does not exist\n");
        return;
    }
    node = fibNodeMake(key);
    if (node == NULL) {
        printf("Cannot make node\n");
        return;
    }
    fibHeapInsert_node(heap, node);
}

//将h1, h2合并成一个堆，并返回合并后的堆
FibHeap* fibHeapUnion(FibHeap *h1, FibHeap *h2) {
    FibHeap *tmp;
    if (h1 == NULL) {
        return h2;
    }
    if (h2 == NULL) {
        return h1;
    }
    //为尽可能的少操作，将h2附加到h1上，保证h1的度数较大 
    if(h2->maxDegree > h1->maxDegree) {
        tmp = h1;
        h1 = h2;
        h2 = tmp;
    }
    if((h1->min) == NULL) {                //h1无最小结点
        h1->min = h2->min;
        h1->keyNum = h2->keyNum;
        free(h2->cons);
        free(h2);
    }
    else if((h2->min) == NULL) {           //h1有最小结点而h2无最小结点
        free(h2->cons);
        free(h2);
    }                                      //h1和h2均有最小结点
    else { 
        //将h2中根链表添加到h1中
        fibNodeCat(h1->min, h2->min);
        if (h1->min->key > h2->min->key) {
            h1->min = h2->min;
        } 
        h1->keyNum += h2->keyNum;
        free(h2->cons);
        free(h2);
    }
    return h1;
}

//将"堆的最小结点"从根链表中移除，即"将最小结点所属的树"从堆中移除
FibNode *fibHeapRemove_min(FibHeap *heap) {
    FibNode *min = heap->min;
    if (heap->min == min->right) {
        heap->min = NULL;
    }
    else {
        fibNodeRemove(min);
        heap->min = min->right;
    }
    min->left = min->right = min;
    return min;
}

//将node链接到root根结点
void fibHeapLink(FibHeap * heap, FibNode * node, FibNode *root) {
    //将node从双链表中移除
    fibNodeRemove(node);
    //将node设为root的孩子
    if (root->child == NULL) {
        root->child = node;
    } 
    else {
        fibNodeAdd(node, root->child);
    }
    node->parent = root;
    root->degree++;
    node->marked = 0;
}

//创建fib_heap_consolidate所需空间
void fibHeapConsInit(FibHeap * heap) {
    int old = heap->maxDegree;
    //计算log2(x)，向上取整
    heap->maxDegree = (int)(log(double(heap->keyNum)) / log(2.0)) + 1;
    //如果原本空间不够，则再次分配内存
    if (old >= heap->maxDegree) {
        return;
    }
    //因为度为heap->maxDegree可能被合并，所以要maxDegree+1
    heap->cons = (FibNode **)realloc(heap->cons, sizeof(FibHeap *) * (heap->maxDegree + 1));
}

//合并斐波那契堆的根链表中左右相同度数的树
void fibHeapConsolidate(FibHeap *heap) {
    //开辟所用空间
    fibHeapConsInit(heap);
    int i;
    int D = heap->maxDegree + 1;
    for (i = 0; i < D; i++) {
        heap->cons[i] = NULL;
    }
    //合并相同度的根结点，使每个度数的树唯一
    while (heap->min != NULL) {
        FibNode *x = fibHeapRemove_min(heap);    //取出堆中的最小树(最小结点所在的树)
        int d = x->degree;                       //获取最小树的度数
        //heap->cons[d] != NULL，意味着有两棵树(x和y)的"度数"相同。
        while (heap->cons[d] != NULL) {
            FibNode *y = heap->cons[d];         //y是"与x的度数相同的树" 
            if (x->key > y->key) {              //保证x的键值比y小
                FibNode *tmp = x;
                x = y;
                y = tmp;
            }
            fibHeapLink(heap, y, x);            //将y链接到x中
            heap->cons[d] = NULL;
            d++;
        }
        heap->cons[d] = x;
    }
    heap->min = NULL;
    //将heap->cons中的结点重新加到根表中
    for (i = 0; i < D; i++) {
        if (heap->cons[i] != NULL) {
            if (heap->min == NULL) {
                heap->min = heap->cons[i];
            }  
            else {
                fibNodeAdd(heap->cons[i], heap->min);
                if ((heap->cons[i])->key < heap->min->key) {
                    heap->min = heap->cons[i];
                } 
            }
        }
    }
}

//移除最小结点min
FibNode* fibHeapExtractMin_node(FibHeap *heap) {
    if (heap==NULL || heap->min==NULL) {
        return NULL;
    }
    FibNode *child = NULL;
    FibNode *min = heap->min;
    //将min每一个儿子(儿子和儿子的兄弟)都添加到"斐波那契堆的根链表"中
    while (min->child != NULL) {
        child = min->child;
        fibNodeRemove(child);
        if (child->right == child) {
            min->child = NULL;
        }  
        else {
            min->child = child->right;
        }
        fibNodeAdd(child, heap->min);
        child->parent = NULL;
    }
    //将min从根链表中移除
    fibNodeRemove(min);
    if (min->right == min) { //若min是堆中唯一结点，则设置堆的最小结点为NULL；
        heap->min = NULL;
    }
    else {                   //否则，设置堆的最小结点为一个非空结点(min->right)，然后再进行调节。
        heap->min = min->right;
        fibHeapConsolidate(heap);
    }
    heap->keyNum--;
    return min;
}

void fibHeapExtractMin(FibHeap *heap) {
    FibNode *node;
    if (heap == NULL || heap->min == NULL) {
        return;
    }
    node = fibHeapExtractMin_node(heap);
    if (node != NULL) {
        free(node);
    }       
}

//修改度数
void renew_degree(FibNode *parent, int degree) {
    parent->degree -= degree;
    if (parent-> parent != NULL)
        renew_degree(parent->parent, degree);
}

//将node从父结点parent的子链接中剥离出来，并使node成为"堆的根链表"中的一员。
void fibHeapCut(FibHeap *heap, FibNode *node, FibNode *parent) {
    fibNodeRemove(node);
    renew_degree(parent, node->degree);
    // node没有兄弟
    if (node == node->right) {
        parent->child = NULL;
    }    
    else {
        parent->child = node->right;
    } 
    node->parent = NULL;
    node->left = node->right = node;
    node->marked = 0;
    // 将"node所在树"添加到"根链表"中
    fibNodeAdd(node, heap->min);
}

//对结点node进行级联剪切
void fibHeapCascadingCut(FibHeap *heap, FibNode *node) {
    FibNode *parent = node->parent;
    if (parent != NULL) {
        return;
    } 
    if (node->marked == 0) {
        node->marked = 1;
    } 
    else {
        fibHeapCut(heap, node, parent);
        fibHeapCascadingCut(heap, parent);
    }
}

//将斐波那契堆heap中结点node的值减少为key
void fibHeapDecrease(FibHeap *heap, FibNode *node, Type key) {
    FibNode *parent;
    if (heap == NULL || heap->min == NULL || node == NULL) {
        return;
    } 
    if (key >= node->key) {
        printf("decrease failed: the new key(%d) is no smaller than current key(%d)\n", key, node->key);
        return ;
    }
    node->key = key;
    parent = node->parent;
    if (parent!=NULL && node->key < parent->key) {
        //将node从父结点parent中剥离出来，并将node添加到根链表中
        fibHeapCut(heap, node, parent);
        fibHeapCascadingCut(heap, parent);
    }
    //更新最小结点
    if (node->key < heap->min->key) {
        heap->min = node;
    } 

}

//将斐波那契堆heap中结点node的值增加为key
void fibHeapIncrease(FibHeap *heap, FibNode *node, Type key) {
    FibNode *child, *parent, *right;
    if (heap == NULL || heap->min == NULL || node == NULL) {
        return;
    } 
    if (key <= node->key) {
        printf("increase failed: the new key(%d) is no greater than current key(%d)\n", key, node->key);
        return;
    }
    //将node每一个儿子(不包括孙子,重孙,...)都添加到"斐波那契堆的根链表"中
    while (node->child != NULL) {
        child = node->child;
        fibNodeRemove(child);               //将child从node的子链表中删除
        if (child->right == child) {
            node->child = NULL;
        } 
        else {
            node->child = child->right;
        } 
        fibNodeAdd(child, heap->min);       //将child添加到根链表中
        child->parent = NULL;
    }
    node->degree = 0;
    node->key = key;
    //如果node不在根链表中，
    //则将node从父结点parent的子链接中剥离出来，
    //并使node成为"堆的根链表"中的一员，
    //然后进行"级联剪切"
    //否则，则判断是否需要更新堆的最小结点
    parent = node->parent;
    if (parent != NULL) {
        fibHeapCut(heap, node, parent);
        fibHeapCascadingCut(heap, parent);
    }
    else if (heap->min == node) {
        right = node->right;
        while (right != node) {
            if (node->key > right->key) {
                heap->min = right;
            }     
            right = right->right;
        }
    }
}

//更新堆heap的结点node的键值为key
void fibHeapNode(FibHeap *heap, FibNode *node, Type key) {
    if (key < node->key) {
        fibHeapDecrease(heap, node, key);
    }     
    else if (key > node->key) {
        fibHeapIncrease(heap, node, key);
    }        
}

//在root中查找键值为key的节点
FibNode* fibNodeSearch(FibNode *root, Type key) {
    FibNode *t = root;    //临时节点
    FibNode *p = NULL;    //要查找的节点
    if (root == NULL) {
        return root;
    } 
    do {
        if (t->key == key) {
            p = t;
            break;
        } 
        else {
            if ((p = fibNodeSearch(t->child, key)) != NULL) {
                break;
            } 
        }    
        t = t->right;
    } while (t != root);
    return p;
}

//在斐波那契堆heap中查找键值为key的节点
FibNode *fibHeapSearch(FibHeap *heap, Type key) {
    if (heap == NULL || heap->min == NULL) {
        return NULL;
    } 
    return fibNodeSearch(heap->min, key);
}

void fibHeapUpdate(FibHeap *heap, Type oldkey, Type newkey) {
    FibNode *node;
    if (heap==NULL) {
        return;
    }  
    node = fibHeapSearch(heap, oldkey);
    if (node != NULL)
        fibHeapNode(heap, node, newkey);
}

//删除结点node
void fibHeapDelete_node(FibHeap *heap, FibNode *node) {
    Type min = heap->min->key;
    fibHeapDecrease(heap, node, min-1);
    fibHeapExtractMin_node(heap);
    free(node);
}

//删除键值为key的结点 
void fibHeapDelete_key(FibHeap *heap, Type key) {
    FibNode *node;
    if (heap == NULL || heap->min == NULL) {
        return;
    } 
    node = fibHeapSearch(heap, key);
    if (node==NULL)
        return ;

    fibHeapDelete_node(heap, node);
}

//从node开始销毁结点 
void fibNodeDestroy(FibNode *node) {
    FibNode *start = node;
    if (node == NULL) {
        return;
    } 
    do {
        fibNodeDestroy(node->child);
        // 销毁node，并将node指向下一个
        node = node->right;
        free(node->left);
    } while(node != start);
}

//销毁斐波那契堆
void fibHeapDestroy(FibHeap *heap) {
    fibNodeDestroy(heap->min);
    free(heap->cons);
    free(heap);
}

//打印斐波那契结点，node为当前结点，prev为当前结点的上一个结点，direction为1标示父结点，为2表示兄弟 
void fibNodePrint(FibNode *node, FibNode *prev, int direction) {
    FibNode *start=node;
    if (node == NULL) {
        return;
    } 
    do {
        if (direction == 1) { 
            printf("%8d(%d) is %2d's child\n", node->key, node->degree, prev->key);
        } 
        else { 
            printf("%8d(%d) is %2d's next\n", node->key, node->degree, prev->key);
        } 
        if (node->child != NULL) { 
            fibNodePrint(node->child, node, 1);
        } 
        // 兄弟结点
        prev = node;
        node = node->right;
        direction = 2;
    } while(node != start);
}

void fibHeapPrint(FibHeap *heap) {
    int i = 0;
    FibNode *p;
    if (heap == NULL || heap->min == NULL) { 
        return;
    } 
    printf("== 斐波那契堆的详细信息: ==\n");
    p = heap->min;
    do {
        i++;
        printf("%2d. %4d(%d) is root\n", i, p->key, p->degree);
        fibNodePrint(p->child, p, 1);
        p = p->right;
    } while (p != heap->min);
    printf("\n");
}

//测试数据a[]，共8个
int a[] = {12,  7, 25, 15, 28, 33, 41, 1};
//测试数据b[]，共14个
int b[] = {18, 35, 20, 42,  9, 31, 23,  6, 48, 11, 24, 52, 13, 2};

//验证插入、抽取最小、减小关键字、合并 
void test() {
    int i;
    int alen = 8;
    int blen = 14;
    FibHeap *ha = fibHeapMake();
    FibHeap *hb = fibHeapMake();
    //Fibonacci堆ha 
    printf("== 斐波那契堆(ha)中依次添加: ");
    for(i = 0; i < alen; i++) {                //验证插入 
        printf("%d ", a[i]);
        fibHeapInsert_key(ha, a[i]);
    }
    printf("\n");

    printf("== 斐波那契堆(ha)删除最小结点\n");     //验证抽取最小
    fibHeapExtractMin(ha);                     
    fibHeapPrint(ha);
    //Fibonacci堆hb 
    printf("== 斐波那契堆(hb)中依次添加: ");
    for(i = 0; i < blen; i++) {
        printf("%d ", b[i]);
        fibHeapInsert_key(hb, b[i]);
    }
    printf("\n");
    printf("== 斐波那契堆(hb)删除最小结点\n");
    fibHeapExtractMin(hb);
    fibHeapPrint(hb);

    printf("== 将20减小为2\n");                    //验证减小关键字 
    fibHeapUpdate(hb, 20, 2);
    fibHeapPrint(hb);

    printf("== 合并ha和hb\n");                     //验证合并 
    ha = fibHeapUnion(ha, hb);
    fibHeapPrint(ha);
    fibHeapDestroy(ha);
}

int main() {
    //验证
    test();
    return 0;
}