数据结构——二项堆（C语言）

女爷i 2022-08-26 00:43 260阅读 0赞

二项堆的合并操作比二叉堆的合并操作复杂度要低，个人觉得二项堆比较难理解，现借此把学习二项堆的笔记写下，这个知识点本人理解的还是不够透彻，希望得到大家的指教。

因为二项堆是一组二项树的集合，学习二项堆时，需要用到二项树的知识点，在这里先讲解下二项树的概念和一些性质。

# 二项树 #

## 定义 ##

二项树采用的是递归定义的有序树，二项树B0只包含一个结点，二项树Bk由两颗二项树Bk-1链接而成：其中一棵树的根是另一棵树的根的最左孩子。

## 二项树Bk的性质 ##

1） 共有2k个结点

2） 树的高度为k

3） 在深度i处恰有Cik个结点，其中i=0,1,...,k

4） 根的度数（子女的个数）为k，它大于任何其他结点的度数；如果根的子女从左到右的编号设为k-1, k-2, …, 0，子女i是子树Bi的根。

## 二项树的结构 ##

![SouthEast][]

# 二项堆 #

## 二项堆定义 ##

二项堆H由一组满足以下性质的二项树组成：

1） H中的每个二项树都遵循最小堆性质：节点的关键字不大于其子节点的关键字。因此，根的关键字最小

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

## 二项堆存储结构 ##

![SouthEast 1][]

## 二项堆的操作 ##

关于二项堆的操作，很多资料给出来伪代码，读者可以根据对伪代码的理解自己编写出源程序，为了方便以后查看，现把个人在参考资料中看到的伪代码附在下面：

1、返回最小关键字节点

由于二项堆中每个二项树都是遵循最小堆性质的，所以最小关键字一定是在根表中，遍历根表一次即可找出最小元素：

BINOMIAL-HEAP-MINIMUM(H)
      y=NIL
      x = head[H]
      min<-  ∞    
     while x!= NIL
          do if key[x] < min
                then min   key[x]
                     y<-  x
             x <- sibling[x]
      return y

2、合并两棵根节点度数相同的二项树

BINOMIAL-LINK(y,z)
    p[y] <- z
    sibling[y] <- child[z]
    child[z] <- y
    degree[z] <- degree[z]+1

3、将H1和H2的根表合并成一个按度数的单调递增次序排列的链表

BINORMIAL-HEAP-MERGE(H1,H2)
              head(H)=NULL
              x=head(H1)
              y=head(H2)
              if(x==NULL)
                   return y
              if(y==NULL)
                   return x               
              if(degree(x)<degree(y))
                       head(H)=x
                      x=sibling(x)
              else
                       head(H)=y
                      y=sibling(y)
              z=head(H)
              while(x!=NULL&&y!=NULL)
                     if(degree(x)<degree(y))
                                 sibling(z)=x
                                 x=sibling(x)
                      else
                                 sibling(z)=y
                                 y=sibling(y)
                      z=sibling(z)
              while(x!=NULL)
                      sibling(z)=x
                      x=sibling(x)
                      z=sibling(z)
               while(y!=NULL)
                      sibling(z)=y
                      y=sibling(y)
                      z=sibling(z)
               return H

4、合并两个二项堆

分四种情况考虑:

Case1：degree\[x\] != degree\[next\_x\]。则只需继续查找，指针沿着根表方向移动。

Case2：degree\[x\] == degree\[next\_x\] == degree\[sibling\[next\_x\]\]。仍不做变化，将指指针沿着根表方向移动。

Case3：degree\[x\] = degree\[next\_x\] != degree\[sibling\[next\_x\]\] ，key\[x\] <= key\[next\_x\]此时，将next\_x连接到x上。

Case4：degree\[x\] = degree\[next\_x\] != degree\[sibling\[next\_x\]\] ，key\[x\] > key\[next\_x\]。此时，将x连接到next\_x上,并更新x，以便进入下一轮迭代。

![SouthEast 2][]![SouthEast 3][]

![SouthEast 4][]

Binomil-Heap-Union伪代码：
      H ←MAKE-BINOMIAL-HEAP()
      head[H] ←BINOMIAL-HEAP-MERGE(H1, H2)
      free theobjects H1 and H2 but not the lists they point to
      if head[H]= NIL
        then return H
      prev-x ←NIL
      x ← head[H]
      next-x ←sibling[x]
      whilenext-x ≠ NIL
        do if (degree[x] ≠ degree[next-x]) or
                   (sibling[next-x] ≠ NIL and degree[sibling[next-x]] = degree[x])
               then prev-x ←x                               ▹ Cases 1 and 2
                   x ← next-x                               ▹ Cases 1 and 2
               else if key[x] ≤ key[next-x]
                     then sibling[x] ←sibling[next-x]          ▹ Case 3
                           BINOMIAL-LINK(next-x,x)              ▹ Case 3
                     else if prev-x =NIL                       ▹ Case 4
                               then head[H] ←next-x             ▹ Case 4
                              else sibling[prev-x] ← next-x       ▹ Case 4
                            BINOMIAL-LINK(x,next-x)              ▹ Case 4
                           x ←next-x                           ▹ Case 4
            next-x ← sibling[x]
      return H

5、插入一个节点

插入节点的操作就是先构造一个只包含一个节点的二项堆H1，再在O（logn）时间内，将其与包含n个节点的二项堆H合并

BINOMIAL-HEAP-INSERT(H,x)
    1  H′ ←MAKE-BINOMIAL-HEAP()
    2  p[x] ←NIL
    3  child[x]← NIL
    4 sibling[x] ← NIL
    5 degree[x] ← 0
    6  head[H′]← x
    7  H ←BINOMIAL-HEAP-UNION(H, H′)

6、抽取最小关键字的节点

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

![SouthEast 5][]

BINOMIAL-HEAP-EXTRACT-MIN(H)
    1、find the root x with the minimum key inthe root list of H
          andremove  x from the root list of H
    2、H’ <- MAKE-BINOMIAL-HEAP()
    3、reverse the order of the linked list ofx’s children, 
    setting the p field of each child to NIL 
    and set head[H’] topoint to the head of the resulting list
    4、H <-BINOMIAL-HEAP-UNION(H,H’)
    5、return x

7、减小关键字的值

该过程就是更新节点的值，将某一节点的关键字值减小为一个新值K，如果K大于当前节点的关键字值，那么报错。但是注意需要维护最小堆的性质。

![SouthEast 6][]

BINOMIAL-HEAP-DECREASE-KEY(H,x, k)
    1 if k >key[x]
    2   then error "new key is greater than current key"
    3 key[x] ← k
    4 y ← x
    5 z ← p[y]
    6 while z ≠ NILand key[y] < key[z]
    7    do exchange key[y] ↔ key[z]
    8       ▸ If y and z have satellite fields,exchange them, too.
    9       y ← z
    10       z ← p[y]

8、删除一个节点

BINOMIAL-HEAP-DELETE(H,x)
    1 BINOMIAL-HEAP-DECREASE-KEY(H, x, -∞)
    2 BINOMIAL-HEAP-EXTRACT-MIN(H)

# 完整程序 #

函数定义：

#ifndef BINOMIAL_HEAP_H_INCLUDED
    #define BINOMIAL_HEAP_H_INCLUDED
    #include<stdio.h>
    #include<malloc.h>
    #include <limits.h>
    #define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
    /*二项堆的ADT*/
    typedef struct node *Binomial_node;
    typedef struct node
    {
        int key;//节点关键字域
        int degree;//节点度数,即节点子女个数
        Binomial_node parent;//父节点指针
        Binomial_node left_child;//节点的最左儿子指针
        Binomial_node sibling;//右兄弟指针
    }BinNode;
    typedef struct Heap *Binomial_Heap;
    typedef struct Heap
    {
        Binomial_node head;
    }BinHeap;
    /*函数声明*/
    Binomial_Heap Make_Binomial_Heap();
    Binomial_node  Binomial_Heap_MinMum(Binomial_Heap heap);
    void Binomial_Tree_Link(Binomial_node y,Binomial_node z);
    Binomial_node Binomial_Heap_Merge(Binomial_Heap H1, Binomial_Heap H2);
    Binomial_Heap Binomial_Heap_Union(Binomial_Heap H1,Binomial_Heap H2);
    Binomial_node Create_node(int key);
    Binomial_Heap  Binomial_Heap_insert(Binomial_Heap heap,Binomial_node x);
    Binomial_node  Binomial_Heap_Extract_Min(Binomial_Heap *heap);
    void Binomial_Heap_Decrease_key(Binomial_Heap  heap,Binomial_node x,int k);
    void Binomial_Heap_Delete(Binomial_Heap *heap,int key);
    Binomial_node BinHeapFind(Binomial_node Node, int key);
    void PrintBinHeap(Binomial_node HNode);
    /*创建并返回一个新的不含任何元素的堆*/
    Binomial_Heap Make_Binomial_Heap()
    {
        Binomial_Heap heap=(Binomial_Heap)malloc(sizeof(BinHeap));
        heap->head=NULL;//头指针为空即可
        return heap;
    }
    /*寻找最小关键字,并返回其指针*/
    Binomial_node Binomial_Heap_MinMum(Binomial_Heap heap)
    {
        Binomial_node y=NULL;
        Binomial_node x=heap->head;
        int min=INT_MAX;
        while(x!=NULL)
        {//找出最小关键字
            if(x->key<min)
            {
                min=x->key;
                y=x;
            }
            x=x->sibling;//沿着根表方向移动
        }
        return y;
    }
    /*合并两棵根节点度数相同的二项树*/
    //将以结点y为根的树与以结点z为根的树连接起来，使z成为y的父结点*/
    void Binomial_Tree_Link(Binomial_node y,Binomial_node z)
    {
        y->parent=z;
        y->sibling=z->left_child;
        z->left_child=y;
        z->degree=z->degree+1;
    }
    /*将H1和H2的根表合并成一个按度数的单调递增次序排列的链表,并返回头节点*/
    Binomial_node Binomial_Heap_Merge(Binomial_Heap H1, Binomial_Heap H2)
    {
        Binomial_Heap H=Make_Binomial_Heap();
        Binomial_node z=NULL;
        Binomial_node x=H1->head;
        Binomial_node y=H2->head;
        if(x==NULL)
            return y;
        if(y==NULL)
            return x;
        if(x->degree<=y->degree)
        {
            H->head=x;
            x=x->sibling;
        }
        else
        {
            H->head=y;
            y=y->sibling;
        }
        z=H->head;
        while(x!=NULL&&y!=NULL)
        {//节点度数递增排列
            if(x->degree<=y->degree)
                {
                    z->sibling=x;
                    x=x->sibling;
                }
           else
            {
                z->sibling=y;
                y=y->sibling;
            }
           z=z->sibling;
        }
        while(x!=NULL)//把剩下的复制即可
        {
            z->sibling=x;
            x=x->sibling;
            z=z->sibling;
        }
        while(y!=NULL)//把剩下的复制即可
        {
            z->sibling=y;
            y=y->sibling;
            z=z->sibling;
        }
        return H->head;
    }
    /*合并两个二项堆*/
    Binomial_Heap Binomial_Heap_Union(Binomial_Heap H1,Binomial_Heap H2)
    {
        Binomial_Heap H=Make_Binomial_Heap();
        H->head=Binomial_Heap_Merge(H1,H2);
        if(NULL==H->head)
            return H;
        Binomial_node x = H->head;
        Binomial_node prev_x = NULL;
        Binomial_node next_x = x->sibling;
        while(next_x!=NULL)
        {
            if((x->degree!=next_x->degree)
               ||(next_x->sibling!=NULL && next_x->sibling->degree==x->degree))
            {
                prev_x=x;
                x=next_x;
            }
            else if(x->key<=next_x->key)
            {
                x->sibling=next_x->sibling;
                Binomial_Tree_Link(next_x,x);
            }
            else
            {
                if(prev_x==NULL)
                {
                    H->head=next_x;
                }
                else
                {
                    prev_x->sibling=next_x;
                }
                Binomial_Tree_Link(x,next_x);
                x=next_x;
            }
            next_x=x->sibling;
        }
        return H;
    }
    /*创建节点*/
    Binomial_node Create_node(int key)
    {
        Binomial_node p;
        p=(Binomial_node)malloc(sizeof(BinNode));
        p->parent=NULL;
        p->left_child=NULL;
        p->sibling=NULL;
        p->degree=0;
        p->key=key;
        return p;
    }
    /*插入节点*/
    Binomial_Heap  Binomial_Heap_insert(Binomial_Heap heap,Binomial_node x)
    {
        Binomial_Heap Hr;
        Hr=Make_Binomial_Heap();
        Hr->head=x;
        Hr=Binomial_Heap_Union(Hr,heap);
        return Hr;
    }
    /*抽取最小关键字的值的节点*/
    Binomial_node Binomial_Heap_Extract_Min(Binomial_Heap *heap)
    {
        Binomial_node y=NULL,prev_y=NULL;
        int MIN=INT_MAX;
        Binomial_node x=(*heap)->head;//x指向根链表
        Binomial_Heap H=Make_Binomial_Heap();
        Binomial_node temp=NULL;
        while(x!=NULL)
        {//找出二项堆中最小关键字值
            if(x->key<MIN)
            {
                MIN=x->key;
                prev_y=y;
                y=x;
            }
            x=x->sibling;
        }
        if(NULL==y)return NULL;
        else//删除最小关键字的值的节点
        {
            if(prev_y==NULL)
                (*heap)->head=(*heap)->head->sibling;
            else
                prev_y->sibling=y->sibling;
        }
        x=y->left_child;//把所删除节点剩下子二项树逆序排序,组成新的二项堆H
        while(x!=NULL)
        {
            temp=x;
            x=x->sibling;
            temp->sibling=H->head;
            H->head=temp;
            temp->parent=NULL;
        }
        *heap=Binomial_Heap_Union(H,*heap);//合并两个二项堆
        return y;//返回删除的节点
    }
    /*减小节点关键字的值*/
    void Binomial_Heap_Decrease_key(Binomial_Heap heap,Binomial_node x,int k)
    {
        int temp;
        Binomial_node y=NULL,z=NULL;
        if(k>x->key)
            return;// error"new key is greater than the current key";
        x->key=k;
        y=x;
        z=y->parent;
        while(NULL!=z && z->key>y->key)
        {
            SWAP(z->key,y->key,temp);
            y=z;
            z=y->parent;
        }
    }
    /*删除一个关键字节点*/
    void Binomial_Heap_Delete(Binomial_Heap *heap,int key)
    {
        Binomial_node x=NULL;
        x=BinHeapFind((*heap)->head,key);
        if(NULL!=x)
        {
             //将节点x的值变为最小，并且排序到二项堆顶
            Binomial_Heap_Decrease_key((*heap),x,-INT_MAX);
            //删除堆顶最小关键字值的节点
            Binomial_Heap_Extract_Min(heap);
        }
    }
    //找出一个关键字
    Binomial_node BinHeapFind(Binomial_node Node, int key)
    {
        Binomial_node x=Node;
        Binomial_node p=NULL;
        if(x->key==key)
          {
            p=x;
            return p;
           }
         if(x->left_child!=NULL&&p==NULL)
             {
               p=BinHeapFind(x->left_child,key);
             }
    
        if(x->sibling!=NULL&&p==NULL)
              {
              p=BinHeapFind(x->sibling,key);
              }
          return p;
    }
    
    //打印输出堆结构
    void PrintBinHeap(Binomial_node HNode)
    {
        if (NULL == HNode)
        {
            return ;
        }
        Binomial_node p = HNode;
    
        while (p != NULL)
        {
            printf(" (");
            printf("%d", p->key);
            //显示其孩子
            if(NULL != p->left_child)
            {
                PrintBinHeap(p->left_child);
            }
            printf(") ");
    
            p = p->sibling;
        }
    }
    #endif // BINOMIAL_HEAP_H_INCLUDED

测试程序：

#include <stdio.h>
    #include <stdlib.h>
    #include"Binomial_heap.h"
    int main()
    {
        int key;
        int i,n;
    
        Binomial_Heap heap;
        heap=Make_Binomial_Heap();
        Binomial_Heap H;
        H=Make_Binomial_Heap();
        printf("Enter the size of heap:");
        scanf("%d",&n);
        printf("\n");
        printf("Enter the key of first heap are:");
        printf("\n");
        for(i=0;i<n;i++)
        {
            scanf("%d",&key);
            Binomial_node nod=Create_node(key);
            heap=Binomial_Heap_insert(heap,nod);
        }
        printf("\n");
        printf("Enter the key of second heap are:");
        printf("\n");
        for(i=0;i<n-4;i++)
        {
            scanf("%d",&key);
            Binomial_node nod=Create_node(key);
            H=Binomial_Heap_insert(H,nod);
        }
        printf("\n");
        printf("The first heap of heap are:\n");
        PrintBinHeap(heap->head);
        printf("\n");
        printf("The second heap of H are:\n");
        PrintBinHeap(H->head);
        printf("\n");
       // H_MIN=Binomial_Heap_MinMum(heap);
        heap=Binomial_Heap_Union(heap,H);
        printf("After union the heap,the heap are:\n");
        PrintBinHeap(heap->head);
        printf("\n");
    
        /*
        Binomial_node y=NULL;
        y=Binomial_Heap_Extract_Min(heap);
        */
        int k=5;
        Binomial_Heap_Decrease_key(heap,heap->head->sibling,k);
        printf("After Decrease_key the heap,the heap are:\n");
        PrintBinHeap(heap->head);
        printf("\n");
        int num;
        printf("Enter the number you want to delete:");
        scanf("%d",&num);
        printf("\n");
        Binomial_Heap_Delete(&heap,num);
        printf("After Delete node of the heap,the heap are:\n");
        PrintBinHeap(heap->head);
        printf("\n");
    
        return 0;
    }

参考文献

**[http://162.105.203.28/course/ada09/students/00748181-LJ-BinomialHeap.pdf][http_162.105.203.28_course_ada09_students_00748181-LJ-BinomialHeap.pdf]**

**[http://blog.csdn.net/mishifangxiangdefeng/article/details/7803088\#t3][http_blog.csdn.net_mishifangxiangdefeng_article_details_7803088_t3]**

**[http://www.cnblogs.com/daniagger/archive/2012/02/17/2355625.html][http_www.cnblogs.com_daniagger_archive_2012_02_17_2355625.html]**

**[http://dsqiu.iteye.com/blog/1714961][http_dsqiu.iteye.com_blog_1714961]**

**[http://www.coders-hub.com/2013/04/c-code-for-binomial-heap-tree.html\#.UyaJ0D-SyEr][http_www.coders-hub.com_2013_04_c-code-for-binomial-heap-tree.html_.UyaJ0D-SyEr]**

[SouthEast]: /images/20220824/5b51f83b3ca3417daa323eaaed453aec.png
[SouthEast 1]: /images/20220824/d25bbb4260be49abaa33475bdbffcff4.png
[SouthEast 2]: https://img-blog.csdn.net/20140318100545015?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY2hlbmhhbnpodW4=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 3]: /images/20220824/3b8194e0fd3a4e14b4f98ea45387bfe4.png
[SouthEast 4]: /images/20220824/ff1c539836ba4fd7aa0f22564ea573c4.png
[SouthEast 5]: /images/20220824/0bd855e671154bf784c79254bf951ee9.png
[SouthEast 6]: /images/20220824/309af46a8045455482683fe0ab5565b4.png
[http_162.105.203.28_course_ada09_students_00748181-LJ-BinomialHeap.pdf]: http://162.105.203.28/course/ada09/students/00748181-LJ-BinomialHeap.pdf
[http_blog.csdn.net_mishifangxiangdefeng_article_details_7803088_t3]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7803088#t3
[http_www.cnblogs.com_daniagger_archive_2012_02_17_2355625.html]: http://www.cnblogs.com/daniagger/archive/2012/02/17/2355625.html
[http_dsqiu.iteye.com_blog_1714961]: http://dsqiu.iteye.com/blog/1714961
[http_www.coders-hub.com_2013_04_c-code-for-binomial-heap-tree.html_.UyaJ0D-SyEr]: http://www.coders-hub.com/2013/04/c-code-for-binomial-heap-tree.html#.UyaJ0D-SyEr