优先队列之二项队列

1 二项队列的结构

二项队列不同于我们已经看到的所有优先队列的实现之处在于，一个二项队列不是一棵堆序的树，而是堆序树的集合，成为森林。堆序树的每一棵树都是有约束的形式，叫做二项树。每一个高度至多存在一棵二项树。高度为0的二项树是一棵单节点树；高度为k的二项树Bk通过一棵二项树BK-1附接到另一棵二项树Bk-1的根上而构成。如下图，B0，B1，B2，B3，B4皆为二项树。而它们合起来就是二项队列。

2.二项队列操作

2.1合并

合并两个二项队列的操作在概念上是容易的操作。我们通过例子进行描述。考虑两个二项队列H1和H2，它们分别具有六个和七个元素。

令H3为H1和H2合并之后的二项队列。由于H1没有高度为0的二项树，而H2有，所以将H2中高度为0的二项树作为H3的一部分。然后我们将高度为1的二项树相加。将H1和H2中高度为1的二项树合并，得到下图。

H1和H2中两棵B1树合并

现在H3没有高度为1的二项树，但存在三棵高度为2的树。即H1和H2原有的两个二项树，以及新合并得到的二项树。我们将一棵高度为2的二项树放到H3中，然后合并其他两个二项树。得到高度为3的二项树。由于H1和H2都没有高度为3的二项树，因此该二项树就成为H3的一部分，合并结束。

2.2 插入

插入实际上就是特殊情形的合并。我们只要创建一棵单节点树并执行一次合并。下面的图演示通过依序插入1到7构成一个二项队列。

2.3 DeleteMin

DeleteMin可以通过首先找到一棵具有最小根的二项树来完成。令该树为Bk，并令原始的优先队列为H。我们从H的森林中除去二项树Bk，并形成新的二项树队列H'。再除掉Bk的根，得到一些二项树B0,B1,B2,...,Bk-1，它们共同形成优先队列H''。合并H'和H''，操作结束。

作为例子，对H3执行一次DeleteMin操作。如下图，它的最小根是12。

删除最小根得到下面的H'和H''。

合并H'和H''就是最后的结果，如下图。

3 二项队列的实现

二项树的每一个节点都将包含数据，第一个儿子以及右兄弟。二项树中的诸儿子以递减次序排序。图2解释图1中的二项队列。

图1

图2

二项队列的结构如下：

typedef struct BinNode *Position,*BinTree;
typedef struct Collection *Binqueue;

struct BinNode
{
    ElementType element;/* 数据 */
    Position leftChild;/* 第一个孩子 */
    Position nextSibling;/* 右兄弟 */
};

struct Collection
{
    int currentSize;/* 二项队列所有节点数目 */
    BinTree theTrees[MAXTREES];
    
};

为了合并两个二项队列，我们需要一个例程来合并两个同样大小的二项树。下图指出两个二项树合并时指针是如何变化的。

程序如下：

/* 合并两棵大小相同的二项树 */

/* 合并两棵大小相同的二项树 */
BinTree combine_trees(BinTree t1,BinTree t2){
    if (t1->element > t2->element){
        BinTree temp = t1;
        t1 = t2;
        t2 = temp;
    }
    t2->nextSibling = t1->leftChild;
    t1->leftChild = t2;
    return t1;
    
}

3.1 头文件

//
//  BinTree.h
//  BinTree
//
//  Created by *xin on 2017/6/1.
//  Copyright © 2017年 Coding365. All rights reserved.
//

#ifndef BinTree_h
#define BinTree_h

#include <stdio.h>
#define MAXTREES 100
#define MAXSIZE 10000

typedef int ElementType;

extern  ElementType const ILLEGAL_VALUE;

typedef struct BinNode *Position,*BinTree;
typedef struct Collection *Binqueue;

struct BinNode
{
    ElementType element;/* 数据 */
    Position leftChild;/* 第一个孩子 */
    Position nextSibling;/* 右兄弟 */
};

struct Collection
{
    int currentSize;/* 二项队列所有节点数目 */
    BinTree theTrees[MAXTREES];
    
};
int is_empty(Binqueue h);
/* 初始化二项队列 */
Binqueue initialize();
/* 插入元素 */
Binqueue insert(ElementType x,Binqueue h);
/* 合并两棵大小相同的二项树 */
BinTree combine_trees(BinTree t1,BinTree t2);
/* 合并两个二项队列 */
Binqueue merge(Binqueue h1,Binqueue h2);
/* 删除二项队列最小元 */
ElementType delete_min(Binqueue h);
/* 遍历 */
void print_heap(Binqueue h);


#endif /* BinTree_h */

3.2 实现文件

//
//  BinTree.c
//  BinTree
//
//  Created by *xin on 2017/6/1.
//  Copyright © 2017年 Coding365. All rights reserved.
//

#include "BinTree.h"
#include <stdlib.h>
#include <limits.h>

ElementType const ILLEGAL_VALUE = INT_MIN;
static void error(char* message){
    printf("%s\n",message);
    exit(EXIT_FAILURE);
}

/* 初始化二项队列 */
Binqueue initialize(){
    Binqueue h = (Binqueue)malloc(sizeof(struct Collection));
    if (h == NULL) error("Out of space!!!");

    int i;
    for (i = 0; i < MAXTREES; i++) {
        h->theTrees[i] = NULL;
    }
    
    return h;
}

/* 插入元素 */
/* 插入实际上就是特殊情况的合并，我们只要创建一课单节点的树并执行一次合并 */
Binqueue insert(ElementType x,Binqueue h){
    if (h == NULL)
        h = initialize();
    BinTree singleTree = (BinTree)malloc(sizeof(struct BinNode));
    if (singleTree == NULL)
        error("Out of Space!!");
    
    singleTree->element = x;
    singleTree->leftChild = NULL;
    singleTree->nextSibling = NULL;
    
    Binqueue h2 = initialize();
    h2->theTrees[0] = singleTree;
    h2->currentSize = 1;
    
    if (is_empty(h))
        h = h2;
    else
        merge(h, h2);
    
    return h;
}

/* 是否空 */
int is_empty(Binqueue h){
    return h == NULL || h->currentSize == 0;
}

/* 合并两棵大小相同的二项树 */
BinTree combine_trees(BinTree t1,BinTree t2){
    if (t1->element > t2->element){
        BinTree temp = t1;
        t1 = t2;
        t2 = temp;
    }
    t2->nextSibling = t1->leftChild;
    t1->leftChild = t2;
    return t1;
    
}
/* 合并两个二项队列 */
Binqueue merge(Binqueue h1,Binqueue h2){
    BinTree t1,t2,carry = NULL;
    int i;/* 二项树的秩 */
    int j;
    
    if (h1->currentSize + h2->currentSize > MAXSIZE)
        error("Merge would exceed capacity");
    h1->currentSize += h2->currentSize;
    
    for (i = 0,j = 1; j <= h1->currentSize; i++,j *= 2) {
        t1 = h1->theTrees[i];
        t2 = h2->theTrees[i];
        switch (!!t1 + 2 * !!t2 + 4 * !!carry) {
            case 0:/* 没有树 */
                break;
            case 1:/* 只有t1 */
                break;
            case 2:/* 只有t2 */
                h1->theTrees[i] = t2;
                h2->theTrees[i] = NULL;
                break;
            case 4:/* 只有carry */
                h1->theTrees[i] = carry;
                carry = NULL;
                break;
            case 3:/* t1和t2 */
                carry = combine_trees(t1, t2);
                h1->theTrees[i] = h2->theTrees[i] = NULL;
                break;
            case 5:/* t1和carry */
                carry = combine_trees(t1, carry);
                h1->theTrees[i] = NULL;
                break;
            case 6:/* t2和carry */
                carry = combine_trees(t2, carry);
                h2->theTrees[i] = NULL;
                break;
            case 7:/* t1,t2和carry */
                h1->theTrees[i] = carry;
                h2->theTrees[i] = NULL;
                carry = combine_trees(t1, t2);
                break;
        }
    }
    return h1;
}
/* 删除二项队列最小元 */
ElementType delete_min(Binqueue h){
    if (is_empty(h))
        return ILLEGAL_VALUE;
    int i,j;
    int minTree;
    Binqueue deletedQueue;
    Position deletedTree,oldRoot;
    ElementType minItem;
    
    minItem = INT_MAX;
    
    /* 查找最小二项树根 */
    for (i = 0; i < MAXTREES; i++) {
        if (h->theTrees[i] && h->theTrees[i]->element < minItem){
            minItem = h->theTrees[i]->element;
            minTree = i;
        }
    }
    
    deletedTree = h->theTrees[minTree];
    oldRoot = deletedTree;
    deletedTree = deletedTree->leftChild;
    free(oldRoot);
    
    deletedQueue = initialize();
    deletedQueue->currentSize = (1 << minTree) - 1;
    for (j = minTree - 1; j >= 0; j--) {
        deletedQueue->theTrees[j] = deletedTree;
        deletedTree = deletedTree->nextSibling;
        deletedQueue->theTrees[j]->nextSibling = NULL;
    }
    
    h->theTrees[minTree] = NULL;/* 将具有最小根的二项树删除 */
    h->currentSize -= deletedQueue->currentSize + 1;/* 减少的节点数整数deletedQueue的节点数加上分离之前的根节点 */
    
    merge(h, deletedQueue);
    return minItem;
    
}

static void print_tree(BinTree t){
    if (t != NULL){
        printf("%d ",t->element);
        print_tree(t->leftChild);
        print_tree(t->nextSibling);
    }
}

/* 遍历 */
void print_heap(Binqueue h){
    int i;
    for(i = 0;i < MAXTREES;i++){
        if (h->theTrees[i] != NULL){
            printf("tree[%d]:",i);
            print_tree(h->theTrees[i]);
            printf("\n");
        }
        
    }
}

3.3 调用

//
//  main.c
//  BinTree
//
//  Created by *xin on 2017/6/1.
//  Copyright © 2017年 Coding365. All rights reserved.
//

#include <stdio.h>
#include "BinTree.h"
int main(int argc, const char * argv[]) {
    
    Binqueue h = initialize();
    h = insert(12, h);
    h = insert(21, h);
    h = insert(24, h);
    h = insert(65, h);
    h = insert(14, h);
    h = insert(26, h);
    h = insert(16, h);
    h = insert(18, h);
    print_heap(h);
    delete_min(h);
    printf("\n");
    print_heap(h);
    
    
    return 0;
}