`

优先队列三大利器——二项堆、斐波那契堆、Pairing 堆

 
阅读更多

 

优先队列三大利器——二项堆、斐波那契堆、Pairing 堆

 

本文内容框架：

写在前面的话

二项堆

二项堆的定义，操作，实现

斐波那契堆

斐波那契堆的定义，操作，实现

Pairing堆

Pairing 堆的定义，操作，实现

小结

写在前面的话

昨天发现，作者辛苦的劳动被一个无耻的人给窃取了——有一个人（csdn ID :qiaqia609）（希望能引以为戒）在CSDN上把本人的很多博文完全粘贴复制过去，直接发表在上竟然标注是原创，有图有真相（链接：http://blog.csdn.net/qiaqia609/article/month/2012/10）


竟然有一篇我在 iteye的博客都没有上首页，在CSDN首页竟然被置顶了，本人顿时很恼火，一度不想继续写下去，严重谴责这种不道德的行为，不敢说什么版权，但是这至少本人的辛苦劳作，很多都写到半夜，所以希望人人能有点意识，支持原创（在另一篇博客有详细叙述）。

 

 

 

好吧，虽然昨晚心情一直没有平复，但是总归还是要写，还是要学习。这篇博文主要介绍二项堆、斐波那契堆、Pairing 堆，都知道只要这三个结构应用实现优先队列的，讲解还是比较详细，参考了很多资料，尤其是Pairing堆很少有讲解，但还是力所能及的写了，虽然可能正确很难保证，其次就是斐波那契堆我对于减小一个关键字的操作的级联剪枝不是很理解（不知道为什么要这么做，难道是为了追求好的时间复杂度）还望高人指点，具体细节在下文会有很多介绍。

 

下面对这三者进行对比

其中(*)Amortized time
(**)With trivial modification to store an additional pointer to the minimum element
(***)Where n is the size of the larger heap

 

二项堆（Binomial Heap）

二项堆（Binomial Heap）是二项树（Binomial Tree）的集合（collection），所以势必要先简要介绍下二项树。关于堆（最小堆）的相关知识，作者已经在堆排序有介绍可以点击查看，这里就不多枚举了。

二项树（Binomial Tree）

二项树（Binomial Tree）是一组多分支树的序列，二项树的递归定义：

  • 二项树的第0棵树只有一个结点；
  • 二项树的第K棵树的子结点由二项树的前面k-1棵组成的。

从以上定义，不难得到下面的结论：

 

  • 二项树的第K棵树有 2k个结点，高度是k；
  • 深度为 d 的结点共有\tbinom n d个结点（从上图就可以看出结点是按二项分布的(1,3,3,1)）

二项堆由一组二项树所构成，这里的二项树需要满足下列条件：

1）H中的每个二项树遵循最小堆的性质。

2）对于任意非负整数k，在H中至多有一棵二项树的根具有度数k。

 

对于性质2，任意高度最多有一棵二项树，这样就可以用二项树的集合唯一地表示任意大小的二项堆，比如13个结点的二项堆H，13的二进制表示为（1101），故H包含了最小堆有序二项树B3， B2和B0， 他们分别有8， 4， 2， 1个结点，即共有13个结点。如下图（另外：二项堆中各二项树的根被组织成一个链表，称之为根表）

二项树的ADT

 

typedef struct BinHeapNode BinNode;
typedef struct BinHeapNode * BinHeap;
typedef struct BinHeapNode * Position;
 
//结点ADT
struct BinHeapNode {
    int key;
    int degree;
    Position parent;
    Position leftChild;
    Position sibling;
};

 

二项dui的操作

1）创建二项堆 

 

BinHeap MakeBinHeap() {
    BinHeap heap = NULL;
    heap = (BinHeap) malloc(sizeof(BinNode));
    if (heap == NULL) {
        puts("Out of the Space");
        exit(1);
    }
    memset(newHeap, 0, sizeof(BinNode));
    return heap;
}

 

2）寻找最小关键字

由于每一个二项树都满足最小堆的性质，所以每个二项树的最小关键字一定在根结点，故只需遍历比较根表的情况就可以。

//返回最小根节点的指针
BinHeap BinHeapMin(BinHeap heap) {
    Position y = NULL, x = heap;
    int min = INT_MAX;
 
    while (x != NULL) {
        if (x->key < min) {
            min = x->key;
            y = x;
        }
        x = x->sibling;
    }
    return y;
}

3）合并两个二项堆

合并两个二项堆有三个函数：

 

BINOMIAL-LINK，连接操作，即将两棵根节点度数相同的二项树Bk-1连接成一棵Bk。伪代码：

BINOMIAL-HEAP-MERGE ，将H1和H2的根表合并成一个按度数的单调递增次序排列的链表。

BINOMIAL-HEAP-UNION，反复连接根节点的度数相同的各二项树。伪代码：

合并操作分为两个阶段：

第一阶段：执行BINOMIAL-HEAP-MERGE，将两个堆H1和H2的根表合并成一个链表H，它按度数排序成单调递增次序。MERGE的时间复杂度O(logn)。n为H1和H2的结点总数。（对于每一个度数值，可能有两个根与其对应，所以第二阶段要把这些相同的根连起来）。

第二阶段：将相等度数的根连接起来，直到每个度数至多有一个根时为止。执行过程中，合并的堆H的根表中至多出现三个根具有相同的度数。（MERGE后H中至多出现两个根具有相同的度数，但是将两个相同度数的根的二项树连接后，可能与后面的至多两棵二项树出现相同的度数的根，因此至多出现三个根具有相同的度数）

 

第二阶段根据当前遍历到的根表中的结点x，分四种情况考虑:

Case1：degree[x] != degree[sibling[x]]。此时，不需要做任何变化，将指针向根表后移动即可。(下图示a)

Case2：degree[x] == degree[sibling[x]] == degree[sibling[sibling[x]]]。此时，仍不做变化，将指针后移。(下图示b)

Case3 & Case4：degree[x] = degree[sibling[x]] != degree[sibling[sibling[x]]] (下图示c和d)

Case3：key[x] <= key[sibling[x]]。此时，将sibling[x]连接到x上。

Case4：key[x] > key[sibling[x]]。此时，将x连接到sibling[x]上。

复杂度：O(logn)， 四个过程变化情况：

 

 

//两个堆合并
BinHeap BinHeapUnion(BinHeap &H1, BinHeap &H2) {
    Position heap = NULL, pre_x = NULL, x = NULL, next_x = NULL;
    heap = BinHeapMerge(H1, H2);
    if (heap == NULL) {
        return heap;
    }
 
    pre_x = NULL;
    x = heap;
    next_x = x->sibling;
 
    while (next_x != NULL) {
        if ((x->degree != next_x->degree) ||//Cases 1 and 2
            ((next_x->sibling != NULL) && (next_x->degree == next_x->sibling->degree))) {
                pre_x = x;
                x = next_x;
        } else if (x->key <= next_x->key) {//Cases 3
            x->sibling = next_x->sibling;
            BinLink(next_x, x);
        } else {//Cases 4
            if (pre_x == NULL) {
                heap = next_x;
            } else {
                pre_x->sibling = next_x;
            }
            BinLink(x, next_x);
            x = next_x;
        }
        next_x = x->sibling;
    }
    return heap;
}
 
//将H1, H2的根表合并成一个按度数的单调递增次序排列的链表
BinHeap BinHeapMerge(BinHeap &H1, BinHeap &H2) {
    //heap->堆的首地址，H3为指向新堆根结点
    BinHeap heap = NULL, firstHeap = NULL, secondHeap = NULL,
        pre_H3 = NULL, H3 = NULL;
 
    if (H1 != NULL && H2 != NULL){
        firstHeap = H1;
        secondHeap = H2;
        //整个while，firstHeap, secondHeap, pre_H3, H3都在往后顺移
        while (firstHeap != NULL && secondHeap != NULL) {
            if (firstHeap->degree <= secondHeap->degree) {
                H3 = firstHeap;
                firstHeap = firstHeap->sibling;
            } else {
                H3 = secondHeap;
                secondHeap = secondHeap->sibling;
            }
 
            if (pre_H3 == NULL) {
                pre_H3 = H3;
                heap = H3;
            } else {
                pre_H3->sibling = H3;
                pre_H3 = H3;
            }
            if (firstHeap != NULL) {
                H3->sibling = firstHeap;
            } else {
                H3->sibling = secondHeap;
            }
        }//while
    } else if (H1 != NULL) {
        heap = H1;
    } else {
        heap = H2;
    }
    H1 = H2 = NULL;
    return heap;
}
 
//使H2成为H1的父节点
void BinLink(BinHeap &H1, BinHeap &H2) {
    H1->parent = H2;
    H1->sibling = H2->leftChild;
    H2->leftChild = H1;
    H2->degree++;
}

4）插入一个结点

先创建只有该结点的二项堆，然后在与原来的二项堆合并。

//用数组内的值建堆
BinHeap MakeBinHeapWithArray(int keys[], int n) {
    BinHeap heap = NULL, newHeap = NULL;
    for (int i = 0; i < n; i++) {
        newHeap = (BinHeap) malloc(sizeof(BinNode));
        if (newHeap == NULL) {
            puts("Out of the Space");
            exit(1);
        }
        memset(newHeap, 0, sizeof(BinNode));
        newHeap->key = keys[i];
        if (NULL == heap) {
            heap = newHeap;
        } else {
            heap = BinHeapUnion(heap, newHeap);
            newHeap = NULL;
        }
    }
    return heap;
}

5）删除最小关键字的结点

从根表中找到最小关键字的结点，将以该结点为根的整棵二项树从堆取出，删除取出的二项树的根，将其剩下的子女倒序排列，组成了一个新的二项堆，再与之前的二项堆合并。  

 

//抽取有最小关键字的结点
BinHeap BinHeapExtractMin(BinHeap &heap) {
    BinHeap pre_y = NULL, y = NULL, x = heap;
    int min = INT_MAX;
    while (x != NULL) {
        if (x->key < min) {
            min = x->key;
            pre_y = y;
            y = x;
        }
        x = x->sibling;
    }
 
    if (y == NULL) {
        return NULL;
    }
 
    if (pre_y == NULL) {
        heap = heap->sibling;
    } else {
        pre_y->sibling = y->sibling;
    }
 
    //将y的子结点指针reverse
    BinHeap H2 = NULL, p = NULL;
    x = y->leftChild;
    while (x != NULL) {
        p = x;
        x = x->sibling;
        p->sibling = H2;
        H2 = p;
        p->parent = NULL;
    }
 
    heap = BinHeapUnion(heap, H2);
    return y;
}

 

 6）减小关键字的值

减小关键字的值其实就是更新关键字的值，实现过程就是维护最小堆的过程。

 

//减少关键字的值
void BinHeapDecreaseKey(BinHeap heap, BinHeap x, int key) {
    if(key > x->key) {
        puts("new key is greaer than current key");
        exit(1); //不为降键
    }
    x->key = key;
 
    BinHeap z = NULL, y = NULL;
    y = x;
    z = x->parent;
    while(z != NULL && z->key > y->key) {
        swap(z->key, y->key);
        y = z;
        z = y->parent;
    }
}

 

7）删除一个关键字

删除一个关键字转换为前面的过程——将该关键字修改为最小值（要维护最小堆的性质），然后变成删除最小关键字的过程。 

 

//删除一个关键字
BinHeap BinHeapDelete(BinHeap &heap, int key) {
    BinHeap x = NULL;
    x = BinHeapFind(heap, key);
    if (x != NULL) {
        BinHeapDecreaseKey(heap, x, INT_MIN);
        return BinHeapExtractMin(heap);
    }
    return x;
}
 
//找出一个关键字
BinHeap BinHeapFind(BinHeap &heap, int key) {
    Position p = NULL, x = NULL;
    p = heap;
    while (p != NULL) {
        if (p->key == key) {
            return p;
        } else {
            if((x =BinHeapFind(p->leftChild, key)) != NULL) {
                return x;
            }
            p = p->sibling;
        }
    }
    return NULL;
}
 

 

二项树的完整实现

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<climits>
using namespace std;
 
typedef struct BinHeapNode BinNode;
typedef struct BinHeapNode * BinHeap;
typedef struct BinHeapNode * Position;
 
//结点ADT
struct BinHeapNode {
    int key;
    int degree;
    Position parent;
    Position leftChild;
    Position sibling;
};
 
//用数组内的值建堆
BinHeap MakeBinHeapWithArray(int keys[], int n);
 
//两个堆合并
BinHeap BinHeapUnion(BinHeap &H1, BinHeap &H2);
 
//将H1, H2的根表合并成一个按度数的单调递增次序排列的链表
BinHeap BinHeapMerge(BinHeap &H1, BinHeap &H2);
 
//使H2成为H1的父节点
void BinLink(BinHeap &H1, BinHeap &H2);
 
//返回最小根节点的指针
BinHeap BinHeapMin(BinHeap heap);
 
//减少关键字的值
void BinHeapDecreaseKey(BinHeap heap, BinHeap x, int key);
 
//删除一个关键字
BinHeap BinHeapDelete(BinHeap &heap, int key);
 
//找出一个关键字
BinHeap BinHeapFind(BinHeap &heap, int key);
 
//打印输出堆结构
void PrintBinHeap(BinHeap heap);
 
//销毁堆
void DestroyBinHeap(BinHeap &heap);
 
//用数组内的值建堆
BinHeap MakeBinHeapWithArray(int keys[], int n) {
    BinHeap heap = NULL, newHeap = NULL;
    for (int i = 0; i < n; i++) {
        newHeap = (BinHeap) malloc(sizeof(BinNode));
        if (newHeap == NULL) {
            puts("Out of the Space");
            exit(1);
        }
        memset(newHeap, 0, sizeof(BinNode));
        newHeap->key = keys[i];
        if (NULL == heap) {
            heap = newHeap;
        } else {
            heap = BinHeapUnion(heap, newHeap);
            newHeap = NULL;
        }
    }
    return heap;
}
 
//两个堆合并
BinHeap BinHeapUnion(BinHeap &H1, BinHeap &H2) {
    Position heap = NULL, pre_x = NULL, x = NULL, next_x = NULL;
    heap = BinHeapMerge(H1, H2);
    if (heap == NULL) {
        return heap;
    }
 
    pre_x = NULL;
    x = heap;
    next_x = x->sibling;
 
    while (next_x != NULL) {
        if ((x->degree != next_x->degree) ||//Cases 1 and 2
            ((next_x->sibling != NULL) && (next_x->degree == next_x->sibling->degree))) {
                pre_x = x;
                x = next_x;
        } else if (x->key <= next_x->key) {//Cases 3
            x->sibling = next_x->sibling;
            BinLink(next_x, x);
        } else {//Cases 4
            if (pre_x == NULL) {
                heap = next_x;
            } else {
                pre_x->sibling = next_x;
            }
            BinLink(x, next_x);
            x = next_x;
        }
        next_x = x->sibling;
    }
    return heap;
}
 
//将H1, H2的根表合并成一个按度数的单调递增次序排列的链表
BinHeap BinHeapMerge(BinHeap &H1, BinHeap &H2) {
    //heap->堆的首地址，H3为指向新堆根结点
    BinHeap heap = NULL, firstHeap = NULL, secondHeap = NULL,
        pre_H3 = NULL, H3 = NULL;
 
    if (H1 != NULL && H2 != NULL){
        firstHeap = H1;
        secondHeap = H2;
        //整个while，firstHeap, secondHeap, pre_H3, H3都在往后顺移
        while (firstHeap != NULL && secondHeap != NULL) {
            if (firstHeap->degree <= secondHeap->degree) {
                H3 = firstHeap;
                firstHeap = firstHeap->sibling;
            } else {
                H3 = secondHeap;
                secondHeap = secondHeap->sibling;
            }
 
            if (pre_H3 == NULL) {
                pre_H3 = H3;
                heap = H3;
            } else {
                pre_H3->sibling = H3;
                pre_H3 = H3;
            }
            if (firstHeap != NULL) {
                H3->sibling = firstHeap;
            } else {
                H3->sibling = secondHeap;
            }
        }//while
    } else if (H1 != NULL) {
        heap = H1;
    } else {
        heap = H2;
    }
    H1 = H2 = NULL;
    return heap;
}
 
//使H2成为H1的父节点
void BinLink(BinHeap &H1, BinHeap &H2) {
    H1->parent = H2;
    H1->sibling = H2->leftChild;
    H2->leftChild = H1;
    H2->degree++;
}
 
//返回最小根节点的指针
BinHeap BinHeapMin(BinHeap heap) {
    Position y = NULL, x = heap;
    int min = INT_MAX;
 
    while (x != NULL) {
        if (x->key < min) {
            min = x->key;
            y = x;
        }
        x = x->sibling;
    }
    return y;
}
 
//抽取有最小关键字的结点
BinHeap BinHeapExtractMin(BinHeap &heap) {
    BinHeap pre_y = NULL, y = NULL, x = heap;
    int min = INT_MAX;
    while (x != NULL) {
        if (x->key < min) {
            min = x->key;
            pre_y = y;
            y = x;
        }
        x = x->sibling;
    }
 
    if (y == NULL) {
        return NULL;
    }
 
    if (pre_y == NULL) {
        heap = heap->sibling;
    } else {
        pre_y->sibling = y->sibling;
    }
 
    //将y的子结点指针reverse
    BinHeap H2 = NULL, p = NULL;
    x = y->leftChild;
    while (x != NULL) {
        p = x;
        x = x->sibling;
        p->sibling = H2;
        H2 = p;
        p->parent = NULL;
    }
 
    heap = BinHeapUnion(heap, H2);
    return y;
}
 
//减少关键字的值
void BinHeapDecreaseKey(BinHeap heap, BinHeap x, int key) {
    if(key > x->key) {
        puts("new key is greaer than current key");
        exit(1); //不为降键
    }
    x->key = key;
 
    BinHeap z = NULL, y = NULL;
    y = x;
    z = x->parent;
    while(z != NULL && z->key > y->key) {
        swap(z->key, y->key);
        y = z;
        z = y->parent;
    }
}
 
//删除一个关键字
BinHeap BinHeapDelete(BinHeap &heap, int key) {
    BinHeap x = NULL;
    x = BinHeapFind(heap, key);
    if (x != NULL) {
        BinHeapDecreaseKey(heap, x, INT_MIN);
        return BinHeapExtractMin(heap);
    }
    return x;
}
 
//找出一个关键字
BinHeap BinHeapFind(BinHeap &heap, int key) {
    Position p = NULL, x = NULL;
    p = heap;
    while (p != NULL) {
        if (p->key == key) {
            return p;
        } else {
            if((x =BinHeapFind(p->leftChild, key)) != NULL) {
                return x;
            }
            p = p->sibling;
        }
    }
    return NULL;
}
 
//打印输出堆结构
void PrintBinHeap(BinHeap heap) {
    if (NULL == heap) {
        return ;
    }
    Position p = heap;
 
    while (p != NULL) {
        printf(" (");
        printf("%d", p->key);
        //显示其孩子
        if(NULL != p->leftChild) {
            PrintBinHeap(p->leftChild);
        }
        printf(") ");
 
        p = p->sibling;
    }
}       
 
int kp1[8] = {12,
               7, 25,
              15, 28, 33, 41};
 
int kp2[20] = {18,
                3, 37,
                6, 8, 29, 10, 44, 30, 23, 2, 48, 31, 17, 45, 32, 24, 50, 55};
 
int kp4[23] = {37, 41,
               10, 28, 13, 77,
               1, 6, 16, 12, 25, 8, 14, 29, 26, 23, 18, 11, 17, 38, 42, 27};
int main() {
    BinHeap H1 = NULL;
    H1 = MakeBinHeapWithArray(kp1, 7);
    puts("第一个二叉堆H1:");
    PrintBinHeap(H1);
 
    BinHeap H2 = NULL;
    H2 = MakeBinHeapWithArray(kp2, 19);
    puts("\n\n第二个二叉堆H2:");
    PrintBinHeap(H2);
 
    BinHeap H3 = NULL;
    H3 = BinHeapUnion(H1, H2);
    puts("\n\n合并H1,H2后，得到H3:");
    PrintBinHeap(H3);
 
    BinHeap H4 = NULL;
    H4 = MakeBinHeapWithArray(kp4, 22);
    puts("\n\n用于测试提取和删除的二叉堆H4:");
    PrintBinHeap(H4);
 
    BinHeap extractNode = BinHeapExtractMin(H4);
    if (extractNode != NULL) {
        printf("\n\n抽取最小的值%d后：\n", extractNode->key);
        PrintBinHeap(H4);
    }
 
    extractNode = BinHeapExtractMin(H4);
    if (extractNode != NULL) {
        printf("\n\n抽取最小的值%d后：\n", extractNode->key);
        PrintBinHeap(H4);
    }
 
    extractNode = BinHeapExtractMin(H4);
    if (extractNode != NULL) {
        printf("\n\n抽取最小的值%d后：\n", extractNode->key);
        PrintBinHeap(H4);
    }
 
    BinHeapDelete(H4, 12);
    puts("\n\n删除12后：");
    PrintBinHeap(H4);
    return 0;
}

 

另外的实现参考参考②。

上述的操作的时间复杂度都是O(lgn)。 

 

斐波那契堆（Fibonacci Heap）

斐波那契堆是一种松散的二项堆，与二项堆的主要区别在于构成斐波那契堆得树可以不是二项树，并且这些树的根排列是无须的（二项堆的根结点排序是按照结点个数排序的，不是按照根结点的大小）。斐波那契堆得优势在于它对建堆、插入、抽取最小关键字、联合等操作能在O(1)的时间内完成（不涉及删除元素的操作仅需要O（1））。这是对二项堆效率的巨大改善。但由于斐波那契堆得常数因子以及程序设计上的复杂度，使它不如通常的二叉堆合适。因此，它的价值仅存在于理论意义上。斐波那契堆的另一个特点就是合并操作只发生在抽取一个结点之后，也就是说斐波那契堆的维护总是会延后的（个人根据代码理解的）。

斐波那契堆结点ADT

结点含有以下域：

1） 父节点p[x]

2） 指向任一子女的指针child[x]——结点x的子女被链接成一个环形双链表，称为x的子女表

3） 左兄弟left[x]

4） 右兄弟right[x]——当left[x] = right[x] = x时，说明x是独子。

5） 子女的个数degree[x]

6） 布尔值域mark[x]——标记是否失去了一个孩子

 

//斐波那契结点ADT
struct FibonacciHeapNode {
    int key;       //结点
    int degree;    //度
    FibonacciHeapNode * left;  //左兄弟
    FibonacciHeapNode * right; //右兄弟
    FibonacciHeapNode * parent; //父结点
    FibonacciHeapNode * child;  //第一个孩子结点
    bool marked;           //是否被删除第1个孩子
};
typedef FibonacciHeapNode FibNode;

 

斐波那契堆ADT

对于一个给定的斐波那契堆H，可以通过指向包含最小关键字的树根的指针min[H]来访问，这个结点被称为斐波那契堆中的最小结点。如果一个斐波那契堆H是空的，则min[H] = NIL. 在一个斐波那契堆中，所有树的根都通过left和right指针链接成一个环形的双链表，称为堆的根表。于是，指针min[H]就指向根表中具有最小关键字的结点（就是查找最小结点的操作，下文就没有再介绍了）。

//斐波那契堆ADT
struct FibonacciHeap {
    int keyNum;   //堆中结点个数
    FibonacciHeapNode * min;//最小堆，根结点
    int maxNumOfDegree;   //最大度
    FibonacciHeapNode * * cons;//指向最大度的内存区域
};
 
typedef FibonacciHeap FibHeap;

斐波那契堆操作

1.创建斐波那契堆

创建一个空的斐波那契堆，过程MAKE-FIB-HEAP 分配并返回一个斐波那契堆对象H； 

 

//初始化一个空的Fibonacci Heap
FibHeap * FibHeapMake() {
    FibHeap * heap = NULL;
    heap = (FibHeap *) malloc(sizeof(FibHeap));
    if (NULL == heap) {
        puts("Out of Space!!");
        exit(1);
    }
    memset(heap, 0, sizeof(FibHeap));
    return heap;
}
 
//初始化结点x
FibNode * FibHeapNodeMake() {
    FibNode * x = NULL;
    x = (FibNode *) malloc(sizeof(FibNode));
    if (NULL == x) {
        puts("Out of Space!!");
        exit(1);
    }
    memset(x, 0, sizeof(FibNode));
    x->left = x->right = x;
    return x;
}

 

2.插入一个结点

要出人一个结点x，对结点的各域初始化，赋值，然后构造自身的环形双向链表后，将x加入H的根表中。 也就是说，结点x 成为一棵单结点的最小堆有序树，同时就是斐波那契堆中一棵无序树而且在根表最小结点的左边。

     如图是将关键字为21的结点插入斐波那契堆。该结点自成一棵最小堆有序树，从而被加入到根表中，成为根的左兄弟。 

 

 

//堆结点x插入fibonacci heap中
void FibHeapInsert(FibHeap * heap, FibNode * x) {
    if (0 == heap->keyNum) {
        heap->min = x;
    } else {
        FibNodeAdd(x, heap->min);
        x->parent = NULL;
        if (x->key < heap->min->key) {
            heap->min = x;
        }
    }
    heap->keyNum++;
}
 
//将数组内的值插入Fibonacci Heap
void FibHeapInsertKeys(FibHeap * heap, int keys[], int keyNum) {
    for (int i = 0; i < keyNum; i++) {
        FibHeapInsertKey(heap, keys[i]);
    }
}
 
//将值插入Fibonacci Heap
static void FibHeapInsertKey(FibHeap * heap, int key) {
    FibNode * x = NULL;
    x = FibHeapNodeMake();
    x->key = key;
    FibHeapInsert(heap, x);
}

 

3.合并两个堆

不同于二项堆，这个操作在斐波那契堆里非常简单。仅仅简单地将H1和H2的两根表串联，然后确定一个新的最小结点。

4.抽取（删除）最小结点

抽取最小结点的操作是斐波那契堆最复杂的操作，就是过程比较多，下面一步一步介绍。

1）将要抽取最小结点的子树都直接串联在根表中，如图（b）

2）然后就是合并所有degree相等的树，直到没有相等的degree的树。

（1）先定义一个数组A，数组A保存的根表子树中的头结点，A[i]=y表示树 y 的degree值是 i 。这样就可以得到数组A的长度就等于当前斐波那契堆中degree的最大值。

（2）当发现两个相等的degree的树，就执行合并操作。“发现”是这样得到的——向右遍历根表的结点，得到当前子树的degree的值，如果该degree值在A数组已经有元素则就是degree相等，就可以合并了。如图（e）（f）就是将degree等于 1的两个子树合并。

 

 

//抽取最小结点
FibNode * FibHeapExtractMin(FibHeap * heap) {
    FibNode * x = NULL, * z = heap->min;
    if (z != NULL) {
 
        //删除z的每一个孩子
        while (NULL != z->child) {
            x = z->child;
            FibNodeRemove(x);
            if (x->right == x) {
                z->child = NULL;
            } else {
                z->child = x->right;
            }
            FibNodeAdd(x, z);//add x to the root list heap
            x->parent = NULL;
        }
 
        FibNodeRemove(z);
        if (z->right == z) {
            heap->min = NULL;
        } else {
            heap->min = z->right;
            FibHeapConsolidate(heap);
        }
        heap->keyNum--;
    }
    return z;
}
 
//合并左右相同度数的二项树
void FibHeapConsolidate(FibHeap * heap) {
    int D, d;
    FibNode * w = heap->min, * x = NULL, * y = NULL;
    FibHeapConsMake(heap);//开辟哈希所用空间
    D = heap->maxNumOfDegree + 1;
    for (int i = 0; i < D; i++) {
        *(heap->cons + i) = NULL;
    }
 
    //合并相同度的根节点，使每个度数的二项树唯一
    while (NULL != heap->min) {
        x = FibHeapMinRemove(heap);
        d = x->degree;
        while (NULL != *(heap->cons + d)) {
            y = *(heap->cons + d);
            if (x->key > y->key) {//根结点key最小
                swap(x, y);
            }
            FibHeapLink(heap, y, x);
            *(heap->cons + d) = NULL;
            d++;
        }
        *(heap->cons + d) = x;
    }
    heap->min = NULL;//原有根表清除
 
    //将heap->cons中结点都重新加到根表中，且找出最小根
    for (int i = 0; i < D; i++) {
        if (*(heap->cons + i) != NULL) {
            if (NULL == heap->min) {
                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);
                }//if(<)
            }//if-else(==)
        }//if(!=)
    }//for(i)
}
 
//将x根结点链接到y根结点
void FibHeapLink(FibHeap * heap, FibNode * x, FibNode *y) {
    FibNodeRemove(x);
    if (NULL == y->child) {
        y->child = x;
    } else {
        FibNodeAdd(x, y->child);
    }
    x->parent = y;
    y->degree++;
    x->marked = false;
}
 
//开辟FibHeapConsolidate函数哈希所用空间
static void FibHeapConsMake(FibHeap * heap) {
    int old = heap->maxNumOfDegree;
    heap->maxNumOfDegree = int(log(heap->keyNum * 1.0) / log(2.0)) + 1;
    if (old < heap->maxNumOfDegree) {
        //因为度为heap->maxNumOfDegree可能被合并,所以要maxNumOfDegree + 1
        heap->cons = (FibNode **) realloc(heap->cons,
            sizeof(FibHeap *) * (heap->maxNumOfDegree + 1));
        if (NULL == heap->cons) {
            puts("Out of Space!");
            exit(1);
        }
    }
}
 
//将堆的最小结点移出，并指向其有兄弟
static FibNode *FibHeapMinRemove(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;
}
 

 

5.减小一个关键字

减小一个关键字的字，会破坏最小堆的性质，所以要进行最小堆维护。因为斐波那契支持减小关键字和删除结点操作，所以斐波那契堆的子树就不一定是二项树了。

减小一个关键字主要进行两个步骤：

1）减小关键字，如果破坏最小堆性质，则将该结点a直接从原来的树移除直接串联在根表中，并将父结点p的mark属性设置成长true。

2）进行级联剪枝：如果当前父结点p的mark属性是true，且p的父结点pp的mark属性也是true，那么将p从pp移除加入到根表中

下图中，黑色的结点表示其mark属性为true，(a)(b)将关键字46减少为15，没有发生级联剪枝；（c,d,e）将35减小为5，发生了级联剪枝操作

//减小一个关键字
void FibHeapDecrease(FibHeap * heap, FibNode * x, int key) {
    FibNode * y = x->parent;
    if (x->key < key) {
        puts("new key is greater than current key!");
        exit(1);
    }
    x->key = key;
 
    if (NULL != y && x->key < y->key) {
        //破坏了最小堆性质，需要进行级联剪切操作
        FibHeapCut(heap, x, y);
        FibHeapCascadingCut(heap, y);
    }
    if (x->key < heap->min->key) {
        heap->min = x;
    }
}
 
//切断x与父节点y之间的链接，使x成为一个根
static void FibHeapCut(FibHeap * heap, FibNode * x, FibNode * y) {
    FibNodeRemove(x);
    renewDegree(y, x->degree);
    if (x == x->right) {
        y->child = NULL;
    } else {
        y->child = x->right;
    }
    x->parent = NULL;
    x->left = x->right = x;
    x->marked = false;
    FibNodeAdd(x, heap->min);
}
 
//级联剪切
static void FibHeapCascadingCut(FibHeap * heap, FibNode * y) {
    FibNode * z = y->parent;
    if (NULL != z) {
        if (y->marked == false) {
            y->marked = true;
        } else {
            FibHeapCut(heap, y, z);
            FibHeapCascadingCut(heap, z);
        }
    }
}
 
//修改度数
void renewDegree(FibNode * parent, int degree) {
    parent->degree -= degree;
    if (parent-> parent != NULL) {
        renewDegree(parent->parent, degree);
    }
}

 6.删除一个结点

删除结点X，首先将X的关键字值减小到比最小结点的值更小（调用减小一个关键字的过程），然后删除（抽取）最小结点就可以了。

//删除结点
void FibHeapDelete(FibHeap * heap, FibNode * x) {
    FibHeapDecrease(heap, x, INT_MIN);
    FibHeapExtractMin(heap);
}

 

斐波那契堆完整实现

 

//说明：
//代码中Fibonacci Heap 用变量heap表示
//结点通常用x，y等表示
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<climits>
using namespace std;
 
//斐波那契结点ADT
struct FibonacciHeapNode {
    int key;       //结点
    int degree;    //度
    FibonacciHeapNode * left;  //左兄弟
    FibonacciHeapNode * right; //右兄弟
    FibonacciHeapNode * parent; //父结点
    FibonacciHeapNode * child;  //第一个孩子结点
    bool marked;           //是否被删除第1个孩子
};
 
typedef FibonacciHeapNode FibNode;
 
//斐波那契堆ADT
struct FibonacciHeap {
    int keyNum;   //堆中结点个数
    FibonacciHeapNode * min;//最小堆，根结点
    int maxNumOfDegree;   //最大度
    FibonacciHeapNode * * cons;//指向最大度的内存区域
};
 
typedef FibonacciHeap FibHeap;
 
/*****************函数申明*************************/
//将x从双链表移除
inline void FibNodeRemove(FibNode * x);
 
//将x堆结点加入y结点之前(循环链表中)
void FibNodeAdd(FibNode * x, FibNode * y);
 
//初始化一个空的Fibonacci Heap
FibHeap * FibHeapMake() ;
 
//初始化结点x
FibNode * FibHeapNodeMake();
 
//堆结点x插入fibonacci heap中
void FibHeapInsert(FibHeap * heap, FibNode * x);
 
//将数组内的值插入Fibonacci Heap
void FibHeapInsertKeys(FibHeap * heap, int keys[], int keyNum);
 
//将值插入Fibonacci Heap
static void FibHeapInsertKey(FibHeap * heap, int key);
 
//抽取最小结点
FibNode * FibHeapExtractMin(FibHeap * heap);
 
//合并左右相同度数的二项树
void FibHeapConsolidate(FibHeap * heap);
 
//将x根结点链接到y根结点
void FibHeapLink(FibHeap * heap, FibNode * x, FibNode *y);
 
//开辟FibHeapConsolidate函数哈希所用空间
static void FibHeapConsMake(FibHeap * heap);
 
//将堆的最小结点移出，并指向其有兄弟
static FibNode *FibHeapMinRemove(FibHeap * heap);
 
//减小一个关键字
void FibHeapDecrease(FibHeap * heap, FibNode * x, int key);
 
//切断x与父节点y之间的链接，使x成为一个根
static void FibHeapCut(FibHeap * heap, FibNode * x, FibNode * y);
 
//级联剪切
static void FibHeapCascadingCut(FibHeap * heap, FibNode * y);
 
//修改度数
void renewDegree(FibNode * parent, int degree);
 
//删除结点
void FibHeapDelete(FibHeap * heap, FibNode * x);
 
//堆内搜索关键字
FibNode * FibHeapSearch(FibHeap * heap, int key);
 
//被FibHeapSearch调用
static FibNode * FibNodeSearch(FibNode * x, int key);
 
//销毁堆
void FibHeapDestory(FibHeap * heap);
 
//被FibHeapDestory调用
static void FibNodeDestory(FibNode * x);
 
//输出打印堆
static void FibHeapPrint(FibHeap * heap);
 
//被FibHeapPrint调用
static void FibNodePrint(FibNode * x);
/************************************************/
 
//将x从双链表移除
inline void FibNodeRemove(FibNode * x) {
    x->left->right = x->right;
    x->right->left = x->left;
}
 
/*
将x堆结点加入y结点之前(循环链表中)
    a …… y
    a …… x …… y
*/
inline void FibNodeAdd(FibNode * x, FibNode * y) {
    x->left = y->left;
    y->left->right = x;
    x->right = y;
    y->left = x;
}
 
//初始化一个空的Fibonacci Heap
FibHeap * FibHeapMake() {
    FibHeap * heap = NULL;
    heap = (FibHeap *) malloc(sizeof(FibHeap));
    if (NULL == heap) {
        puts("Out of Space!!");
        exit(1);
    }
    memset(heap, 0, sizeof(FibHeap));
    return heap;
}
 
//初始化结点x
FibNode * FibHeapNodeMake() {
    FibNode * x = NULL;
    x = (FibNode *) malloc(sizeof(FibNode));
    if (NULL == x) {
        puts("Out of Space!!");
        exit(1);
    }
    memset(x, 0, sizeof(FibNode));
    x->left = x->right = x;
    return x;
}
 
//堆结点x插入fibonacci heap中
void FibHeapInsert(FibHeap * heap, FibNode * x) {
    if (0 == heap->keyNum) {
        heap->min = x;
    } else {
        FibNodeAdd(x, heap->min);
        x->parent = NULL;
        if (x->key < heap->min->key) {
            heap->min = x;
        }
    }
    heap->keyNum++;
}
 
//将数组内的值插入Fibonacci Heap
void FibHeapInsertKeys(FibHeap * heap, int keys[], int keyNum) {
    for (int i = 0; i < keyNum; i++) {
        FibHeapInsertKey(heap, keys[i]);
    }
}
 
//将值插入Fibonacci Heap
static void FibHeapInsertKey(FibHeap * heap, int key) {
    FibNode * x = NULL;
    x = FibHeapNodeMake();
    x->key = key;
    FibHeapInsert(heap, x);
}
 
//抽取最小结点
FibNode * FibHeapExtractMin(FibHeap * heap) {
    FibNode * x = NULL, * z = heap->min;
    if (z != NULL) {
 
        //删除z的每一个孩子
        while (NULL != z->child) {
            x = z->child;
            FibNodeRemove(x);
            if (x->right == x) {
                z->child = NULL;
            } else {
                z->child = x->right;
            }
            FibNodeAdd(x, z);//add x to the root list heap
            x->parent = NULL;
        }
 
        FibNodeRemove(z);
        if (z->right == z) {
            heap->min = NULL;
        } else {
            heap->min = z->right;
            FibHeapConsolidate(heap);
        }
        heap->keyNum--;
    }
    return z;
}
 
//合并左右相同度数的二项树
void FibHeapConsolidate(FibHeap * heap) {
    int D, d;
    FibNode * w = heap->min, * x = NULL, * y = NULL;
    FibHeapConsMake(heap);//开辟哈希所用空间
    D = heap->maxNumOfDegree + 1;
    for (int i = 0; i < D; i++) {
        *(heap->cons + i) = NULL;
    }
 
    //合并相同度的根节点，使每个度数的二项树唯一
    while (NULL != heap->min) {
        x = FibHeapMinRemove(heap);
        d = x->degree;
        while (NULL != *(heap->cons + d)) {
            y = *(heap->cons + d);
            if (x->key > y->key) {//根结点key最小
                swap(x, y);
            }
            FibHeapLink(heap, y, x);
            *(heap->cons + d) = NULL;
            d++;
        }
        *(heap->cons + d) = x;
    }
    heap->min = NULL;//原有根表清除
 
    //将heap->cons中结点都重新加到根表中，且找出最小根
    for (int i = 0; i < D; i++) {
        if (*(heap->cons + i) != NULL) {
            if (NULL == heap->min) {
                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);
                }//if(<)
            }//if-else(==)
        }//if(!=)
    }//for(i)
}
 
//将x根结点链接到y根结点
void FibHeapLink(FibHeap * heap, FibNode * x, FibNode *y) {
    FibNodeRemove(x);
    if (NULL == y->child) {
        y->child = x;
    } else {
        FibNodeAdd(x, y->child);
    }
    x->parent = y;
    y->degree++;
    x->marked = false;
}
 
//开辟FibHeapConsolidate函数哈希所用空间
static void FibHeapConsMake(FibHeap * heap) {
    int old = heap->maxNumOfDegree;
    heap->maxNumOfDegree = int(log(heap->keyNum * 1.0) / log(2.0)) + 1;
    if (old < heap->maxNumOfDegree) {
        //因为度为heap->maxNumOfDegree可能被合并,所以要maxNumOfDegree + 1
        heap->cons = (FibNode **) realloc(heap->cons,
            sizeof(FibHeap *) * (heap->maxNumOfDegree + 1));
        if (NULL == heap->cons) {
            puts("Out of Space!");
            exit(1);
        }
    }
}
 
//将堆的最小结点移出，并指向其有兄弟
static FibNode *FibHeapMinRemove(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;
}
 
//减小一个关键字
void FibHeapDecrease(FibHeap * heap, FibNode * x, int key) {
    FibNode * y = x->parent;
    if (x->key < key) {
        puts("new key is greater than current key!");
        exit(1);
    }
    x->key = key;
 
    if (NULL != y && x->key < y->key) {
        //破坏了最小堆性质，需要进行级联剪切操作
        FibHeapCut(heap, x, y);
        FibHeapCascadingCut(heap, y);
    }
    if (x->key < heap->min->key) {
        heap->min = x;
    }
}
 
//切断x与父节点y之间的链接，使x成为一个根
static void FibHeapCut(FibHeap * heap, FibNode * x, FibNode * y) {
    FibNodeRemove(x);
    renewDegree(y, x->degree);
    if (x == x->right) {
        y->child = NULL;
    } else {
        y->child = x->right;
    }
    x->parent = NULL;
    x->left = x->right = x;
    x->marked = false;
    FibNodeAdd(x, heap->min);
}
 
//级联剪切
static void FibHeapCascadingCut(FibHeap * heap, FibNode * y) {
    FibNode * z = y->parent;
    if (NULL != z) {
        if (y->marked == false) {
            y->marked = true;
        } else {
            FibHeapCut(heap, y, z);
            FibHeapCascadingCut(heap, z);
        }
    }
}
 
//修改度数
void renewDegree(FibNode * parent, int degree) {
    parent->degree -= degree;
    if (parent-> parent != NULL) {
        renewDegree(parent->parent, degree);
    }
}
 
//删除结点
void FibHeapDelete(FibHeap * heap, FibNode * x) {
    FibHeapDecrease(heap, x, INT_MIN);
    FibHeapExtractMin(heap);
}
 
//堆内搜索关键字
FibNode * FibHeapSearch(FibHeap * heap, int key) {
    return FibNodeSearch(heap->min, key);
}
 
//被FibHeapSearch调用
static FibNode * FibNodeSearch(FibNode * x, int key) {
    FibNode * w = x, * y = NULL;
    if (x != NULL) {
        do {
            if (w->key == key) {
                y = w;
                break;
            } else if (NULL != (y = FibNodeSearch(w->child, key))) {
                break;
            }
            w = w->right;
        } while (w != x);
    }
    return y;
}
 
//销毁堆
void FibHeapDestory(FibHeap * heap) {
    FibNodeDestory(heap->min);
    free(heap);
    heap = NULL;
}
 
//被FibHeapDestory调用
static void FibNodeDestory(FibNode * x) {
    FibNode * p = x, *q = NULL;
    while (p != NULL) {
        FibNodeDestory(p->child);
        q = p;
        if (p -> left == x) {
            p = NULL;
        } else {
            p = p->left;
        }
        free(q->right);
    }
}
 
//输出打印堆
static void FibHeapPrint(FibHeap * heap) {
    printf("The keyNum = %d\n", heap->keyNum);
    FibNodePrint(heap->min);
    puts("\n");
};
 
//被FibHeapPrint调用
static void FibNodePrint(FibNode * x) {
    FibNode * p = NULL;
    if (NULL == x) {
        return ;
    }
    p = x;
    do {
        printf(" (");
        printf("%d", p->key);
        if (p->child != NULL) {
            FibNodePrint(p->child);
        }
        printf(") ");
        p = p->left;
    }while (x != p);
}
 
int keys[10] = {1, 2, 3, 4, 5, 6, 7, 9, 10, 11};
 
int main() {
    FibHeap * heap = NULL;
    FibNode * x = NULL;
    heap = FibHeapMake();
    FibHeapInsertKeys(heap, keys, 10);
    FibHeapPrint(heap);
 
    x = FibHeapExtractMin(heap);
    printf("抽取最小值%d之后：\n", x->key);
    FibHeapPrint(heap);
 
    x = FibHeapSearch(heap, 11);
    if (NULL != x) {
        printf("查找%d成功,", x->key);
        FibHeapDecrease(heap, x, 8);
        printf("减小到%d后：\n", x->key);
        FibHeapPrint(heap);
    }
 
    x = FibHeapSearch(heap, 7);
    if (NULL != x) {
        printf("删除%d成功:\n", x->key);
        FibHeapDelete(heap, x);
        FibHeapPrint(heap);
    }
 
    FibHeapDestory(heap);
    return 0;
}

 

Pairing Heap

斐波那契堆主要有两个缺点：编程实现难度较大和实际效率没有理论的那么快（由于它的存储结构和四个指针）。Pairing Heap的提出就是弥补斐波那契堆的两个缺点——编程简单操作的时间复杂度和斐波那契堆一样。

Pairing Heap其实就是一个具有堆（最大堆或最小堆）性质的树，它的特性不是由它的结构决定的，而是由于它的操作（插入，合并，减小一个关键字等）决定的。

 

Pairing Heap的ADT

 

typedef struct PairingHeapNode
{
	int							key;
	struct	PairingHeapNode*	child;
	struct	PairingHeapNode*	sibling;
	struct	PairingHeapNode*	prev;

}PairHeap;

 

Pairing Heap 的操作

注意：图解过程是以最大堆来演示的，但是代码是以最小堆来写的，见谅！

1.合并两个子堆


static PairHeap* merge_subheaps(PairHeap *p, PairHeap *q)
{
	if(q == NULL)
		return p;
	else if(p->key <= q->key)
	{
		q->prev = p;
		p->sibling = q->sibling;
		if(p->sibling != NULL)
			p->sibling->prev = p;

		q->sibling = p->child;
		if(q->sibling != NULL)
			q->sibling->prev = q;

		p->child = q;
		return p;
	}
	else
	{
		q->prev = p->prev;
		p->prev = q;
		p->sibling = q->child;
		if(p->sibling != NULL)
			p->sibling->prev = p;

		q->child = p;
		return q;
	}
}
 

 

2. 插入一个结点


PairHeap* PairHeap_insert(PairHeap *p, int key)
{
	PairHeap *node;

	node = (PairHeap*)malloc(sizeof(*node));
	if(node == NULL)
		return NULL;

	node->key = key;
	node->child = node->sibling = node->prev = NULL;

	if(p == NULL)
		return node;
	else
		return merge_subheaps(p, node);
}

3.增加（减小）一个关键字


 


PairHeap* PairHeap_DecreaseKey(PairHeap *p, PairHeap *pos, int d)
{
	if(d < 0)
		return p;

	pos->key = pos->key - d;
	if(p == pos)
		return p;

	if(pos->sibling != NULL)
		pos->sibling->prev = pos->prev;

	if(pos->prev->child = pos)
		pos->prev->child = pos->sibling;
	else
		pos->prev->sibling = p->sibling;

	p->sibling = NULL;
	return merge_subheaps(p, pos);
} 

5.删除最小结点


 

 

Pairing Heap完整实现

 

#include <stdlib.h>

typedef struct PairingHeapNode
{
	int							key;
	struct	PairingHeapNode*	child;
	struct	PairingHeapNode*	sibling;
	struct	PairingHeapNode*	prev;

}PairHeap;

static PairHeap* merge_subheaps(PairHeap *p, PairHeap *q);
static PairHeap* combine_siblings(PairHeap *p);

PairHeap* PairHeap_insert(PairHeap *p, int key)
{
	PairHeap *node;

	node = (PairHeap*)malloc(sizeof(*node));
	if(node == NULL)
		return NULL;

	node->key = key;
	node->child = node->sibling = node->prev = NULL;

	if(p == NULL)
		return node;
	else
		return merge_subheaps(p, node);
}

PairHeap* PairHeap_DecreaseKey(PairHeap *p, PairHeap *pos, int d)
{
	if(d < 0)
		return p;

	pos->key = pos->key - d;
	if(p == pos)
		return p;

	if(pos->sibling != NULL)
		pos->sibling->prev = pos->prev;

	if(pos->prev->child = pos)
		pos->prev->child = pos->sibling;
	else
		pos->prev->sibling = p->sibling;

	p->sibling = NULL;
	return merge_subheaps(p, pos);
}

PairHeap* PairHeap_DeleteMin(int *key, PairHeap *p)
{
	PairHeap *new_root;

	if(p == NULL)
		return NULL;
	else
	{
		*key = p->key;
		if(p->child != NULL)
			new_root = combine_siblings(p->child);

		free(p);
	}
	return new_root;
}

static PairHeap* combine_siblings(PairHeap *p)
{
	PairHeap *tree_array[1024];
	int i, count;

	if(p->sibling == NULL)
		return p;

	for(count = 0; p != NULL; count++)
	{
		tree_array[count] = p;
		p->prev->sibling = NULL;
		p = p->sibling;
	}
	tree_array[count] = NULL;

	for(i = 1; i < count; i++)
		tree_array[i] = merge_subheaps(tree_array[i-1], tree_array[i]);

	return tree_array[count-1];
}

static PairHeap* merge_subheaps(PairHeap *p, PairHeap *q)
{
	if(q == NULL)
		return p;
	else if(p->key <= q->key)
	{
		q->prev = p;
		p->sibling = q->sibling;
		if(p->sibling != NULL)
			p->sibling->prev = p;

		q->sibling = p->child;
		if(q->sibling != NULL)
			q->sibling->prev = q;

		p->child = q;
		return p;
	}
	else
	{
		q->prev = p->prev;
		p->prev = q;
		p->sibling = q->child;
		if(p->sibling != NULL)
			p->sibling->prev = p;

		q->child = p;
		return q;
	}
}
 

 

小结

终于到小结了，这篇文章写得比较吃力，如斐波那契堆的“减小一个关键字”的操作我就对使用级联剪切还没有找到解释，还有还没有找到Pairing Heap的定义，唯独只有自己理解和揣测（比如pairing heap没有明确的定义，本人个人理解pairing heap的独特性一定在他的操作，即行为决定特征）但总归还是相对完整，希望能对你有说帮助。如果你有任何建议、批评或补充，还请你不吝提出，不甚感激。更多参考请移步互联网。

 

 

 

 

参考：

①酷~行天下： http://mindlee.net/2011/09/26/binomial-heaps/

②Björn B. Brandenburg： http://www.cs.unc.edu/~bbb/#binomial_heaps

③酷~行天下： http://mindlee.net/2011/09/29/fibonacci-heaps/

④Adoo's blog ： http://www.roading.org/algorithm/introductiontoalgorithm/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E5%A0%86fibonacci-heaps.html

⑤Golden_Shadow： http://blog.csdn.net/golden_shadow/article/details/6216921

⑥Sartaj Sahni： http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c13/pairing.htm

⑦C++ template Fibonacci heap, with demonstration： http://ideone.com/9jYnv

⑧"The pairing heap: a new form of self-adjusting heap"： http://www.cs.cmu.edu/afs/cs.cmu.edu/user/sleator/www/papers/pairing-heaps.pdf

⑨Vikas Tandi ： http://programmingpraxis.com/2009/08/14/pairing-heaps/

⑩http://www.cise.ufl.edu/~sahni/cop5536/slides/lec156.pdf

⑩+1： 算法导论和维基百科

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

15
顶
3
踩
分享到：
| 排序算法群星豪华大汇演
评论
18 楼 970655147 2015-08-03  
BinHeapExtractMin 函数中, 的prev_y是否应该是y结点的前一个结点, 而非y结点之前的最小的结点呢?
17 楼 970655147 2015-08-03  
博主 BinHeapMerge归并的逻辑，first 或者second 为空之后的处理，应该放在放在循环外面好点吧
16 楼 DSQiu 2015-06-16  
psfu 写道
看那个抄袭的貌似删了已经，鄙视他这种行为

谢谢您，感动ing
15 楼 psfu 2015-06-16  
看那个抄袭的貌似删了已经，鄙视他这种行为
14 楼 jxxfldt 2014-03-29  
关于二项堆有个问题，为什么在合并的过程case2中，x,next_x,sibling(next_x)的读相同时，要指针后移？直接将next_x作为x的父节点（或者x作为next_x的父节点）不可以吗？不太清楚。
13 楼 cxz501177639 2013-03-23  
在斐波那契堆中，个人怎么总觉得LZ这个函数renewDegree写错了，因为在（a)中，结点24一开始的深度为2，如果将24改为5的话，FibHeapCut函数切断该结点时，按照LZ中的renewDegree看来，24的父结点7的深度变成了1，但其实它的深度应该是2吧？  
12 楼 DSQiu 2012-11-05  
guji528 写道
支持原创。写文章都很累了，还是去防备自己写的东西被别人占用、更累了。

是呀，每写一篇文章都要话费很大的心思和精力……
11 楼 guji528 2012-11-05  
支持原创。写文章都很累了，还是去防备自己写的东西被别人占用、更累了。
10 楼 DSQiu 2012-11-05  
lection.yu 写道
辛苦了。那些人脸皮太厚了。

嗯嗯，谢谢……
9 楼 lection.yu 2012-11-05  
辛苦了。那些人脸皮太厚了。
8 楼 DSQiu 2012-11-05  
jiang_918 写道
支持！支持！

谢谢，更多惊喜，敬请期待……
7 楼 jiang_918 2012-11-05  
支持！支持！
6 楼 DSQiu 2012-11-03  
max117 写道
支持楼主写下去，这才是纯技术流文章。
楼主的排版跟代码都很清晰，这一点很不容易。

嗯，谢谢，突然发现@max117真懂我……
5 楼 DSQiu 2012-11-03  
javaboy8282 写道
让咱这数学不好的情以何堪哇   不过楼主真的很强大  顶了

谢谢，加油……
4 楼 javaboy8282 2012-11-03  
让咱这数学不好的情以何堪哇   不过楼主真的很强大  顶了
3 楼 max117 2012-11-03  
支持楼主写下去，这才是纯技术流文章。
楼主的排版跟代码都很清晰，这一点很不容易。
2 楼 DSQiu 2012-11-03  
cometzb_xujun 写道
厉害！！厉害

谢谢你的鼓励，我会继续努力，争取写得更好……
1 楼 cometzb_xujun 2012-11-03  
厉害！！厉害
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    二项式堆、斐波纳契(Fibonacci)堆和Pairing堆

    二项式堆、斐波纳契堆和Pairing堆是数据结构中的三种高效优先队列实现，它们在处理大量数据的排序、最优化问题以及图形算法等领域有着广泛的应用。这三类堆都属于堆数据结构，但各自具有不同的特性和操作效率。 1. ...

    二叉堆（最小堆）+二项堆+斐波那契堆

    二叉堆、二项堆和斐波那契堆是数据结构中的重要概念，它们都是堆数据结构的不同变体，主要用于高效地实现某些特定操作，如查找最大或最小元素、优先队列以及各种排序算法。在C++编程语言中，理解和实现这些堆结构...

    datastructure_斐波那契堆_二项堆_

    在这个主题中，我们将深入探讨两种重要的数据结构——斐波那契堆（Fibonacci Heap）和二项堆（Binary Heap）。它们在算法设计，特别是图论和最优化问题中扮演着至关重要的角色，比如Prim's最小生成树算法和Dijkstra'...

    pairing堆的实现参考源码

    Pairing堆是一种特殊的堆数据结构，它在保持了二叉堆简单性的同时，引入了斐波那契堆的高效操作特性。在计算机科学中，堆通常用于优先队列的实现，其中快速插入、删除最小元素以及合并操作是关键。Pairing堆通过其...

    优先队列(1).zip

    常见的优先队列实现有二叉堆、斐波那契堆、跳跃表等。 二叉堆是一种常见的优先队列实现方式，分为最大堆和最小堆。在最大堆中，父节点的值总是大于或等于其子节点的值，因此根节点总是具有最高优先级；相反，最小堆...

    20151910042-刘鹏-DSA实验09-优先队列结构实验1

    4. **二项队列（Binomial Heap）**：二项队列是一种合并操作高效的优先队列实现，由多个二叉堆组成，插入和合并操作的时间复杂度为O(1)，删除最小元素为O(log n)。 5. **斐波那契堆（Fibonacci Heap）**：斐波那契...

    斐波那契堆（fibonacci）

    2. 删除最小元素：斐波那契堆通过“瀑布修剪”（Fibonacci Heap Deletion）策略来优化这个操作。当删除最小元素时，会将所有与其相邻的子节点提升到其位置，这个过程可能引发树的重构，但总体上保证了操作的时间...

    优先队列是一种数据结构.pdf

    例如，可以考虑使用斐波那契堆等其他数据结构或算法优化技术来进一步提升优先队列的性能。此外，随着大数据和云计算的发展，优先队列在分布式系统和大规模数据处理中的应用也将成为新的研究热点。

    斐波那契堆（fibheaps）讲解：背景和分析

    传统的优先队列通常基于二项堆实现。二项堆支持以下操作： - 插入：\( O(\log n) \) - 删除最小值：\( O(\log n) \) - 减小键值：\( O(\log n) \) 在解决最短路径或最小生成树问题时，这些操作的效率直接影响到...

    算法-树形结构- 优先队列.rar

    2. ** Fibonacci Heap**：Fibonacci堆是一种更高效的优先队列实现，尤其在进行多次删除操作时。它通过合并操作减少了每次删除操作的开销，使得总体时间复杂度达到线性。Fibonacci堆由多个堆组成，每个堆都是一个二叉...

    算法面试通关40讲完整课件 11-13 优先队列（PriorityQueue）

    - 斐波那契堆（Fibonacci Heap）：进一步优化了二项堆，降低了操作的时间复杂度。 在面试中，理解和掌握优先队列的概念及其基本操作是至关重要的，因为它们经常出现在算法题目的解决方案中，也是评估候选人数据...

    斐波那契堆（Fibonacci Heap）

    斐波那契堆（Fibonacci Heap）是一种高级的数据结构，主要用于解决图的最短路径问题、优先队列等需要高效插入、删除和查找最小元素的操作。它由计算机科学家Michael L. Fredman和Robert E. Tarjan在1984年提出，其...

    斐波那契堆ppt（中文）

    斐波那契堆是一种高效的优先队列数据结构，主要用于图的最小生成树算法，如Prim算法和Kruskal算法，以及Dijkstra最短路径算法。它由计算机科学家Frederick S.~Tarjan提出，其设计灵感来源于自然界中的斐波那契数列。...

    优先队列

    根据提供的文件信息，可以看出这是一段与加密技术相关的C++代码片段，主要涉及到了优先队列的概念并未在代码中直接体现出来。但是基于题目要求，我们可以从“优先队列”这个概念出发，结合代码中涉及的技术背景（如...

    斐波那契堆的C#实现

    斐波那契堆是一种高效的优先队列数据结构，它在许多高级算法中，如Dijkstra's最短路径算法和Prim's最小生成树算法，扮演着关键角色。在C#编程环境中，实现斐波那契堆可以帮助我们提升这些算法的性能。下面我们将详细...

    斐波那契堆

    传统的堆结构（如二项堆）可以用于实现优先队列，但它们在减少键值（decrease-key）操作上的效率较低。为了改进这一点，引入了斐波那契堆。斐波那契堆的特点包括： - **插入操作**：\(O(1)\)的时间复杂度。 - **...

    二项堆（Binomial Heap）

    二项堆是一种特殊的树形数据结构，用于实现堆排序和优先队列等算法。它由一组二项树组成，每棵树的度数（即子节点个数）最多为2的幂次方。二项堆的概念最早由Frederickson和Gibbons在1984年提出，其设计目标是优化堆...

    斐波那契堆python实现

    斐波那契堆的python实现(优先队列)，实现内容：merge(H), insert(v), find_min() # extractMin(), coalesce_step(), updateMin() # decreaseKey(v,k), delete(v)

    斐波那契数列——队列求解

    4阶斐波那契序列如下：f0=f1=f2=0, f3=1,…,fi=fi-1+fi-2+fi-3+fi-4， 利用容量为k=4的循环队列，构造序列的前n+1项（f0, f1 , f2 ,… fn ），要求满足fn ≤200而fn+1 &gt;200。

    Java Methods-Heaps and Priority Queues.ppt

    Java堆和优先队列 Java堆和优先队列是数据结构中两个重要的概念，在Java编程中经常被使用。在本文中，我们将详细介绍Java堆和优先队列的定义、实现和应用。 一、堆（Heap） 堆是一种特殊的二叉树，它能够实现优先...

Magicbox
Global site tag (gtag.js) - Google Analytics