优先队列——二项队列（binominal queue）（2） capacity, include

yuyang911220

【3】 source code and printing results3.1）source code at a glance
Attention）二项队列的实现源代码用到了 儿子兄弟表示法；
[url=][/url]
#include "binominal_queue.h" #define MINIMAL 10000int minimal(BinominalQueue bq){    int capacity;    int i;    int minimal;    int miniIndex;        minimal = MINIMAL;    capacity = bq->capacity;    for(i=0; i<capacity; i++)    {        if(bq->trees && bq->trees->value < minimal)        {            minimal = bq->trees->value;            miniIndex = i;        }    }    return miniIndex;}// initialize the BinominalQueue with given capacity.BinominalQueue init(int capacity){    BinominalQueue queue;                BinominalTree* trees;     int i;    queue = (BinominalQueue)malloc(sizeof(struct BinominalQueue));    if(!queue)    {        Error("failed init, for out of space !");        return queue;    }        queue->capacity = capacity;        trees = (BinominalTree*)malloc(capacity * sizeof(BinominalTree));    if(!trees)    {        Error("failed init, for out of space !");        return NULL;    }        queue->trees = trees;    for(i=0; i<capacity; i++)    {        queue->trees = NULL;    }        return queue;}  // attention: the root must be the left child of the binominal tree.int getHeight(BinominalTree root){    int height;            if(root == NULL)    {                return 0;            }    height = 1;        while(root->nextSibling)    {        height++;        root = root->nextSibling;    }    return height;}// merge BinominalQueue bq2 into bq1.void outerMerge(BinominalQueue bq1, BinominalQueue bq2){    int height;    int i;    for(i=0; i<bq2->capacity; i++)    {        height = -1;        if(bq2->trees)        {            height = getHeight(bq2->trees->leftChild);                // attention for the line above            // height = height(bq2->trees->leftChild); not height = height(bq2->trees);            merge(bq2->trees, height, bq1);        }                        }        }// merge tree h1 and h2 = bq->trees[height], // who represents the new tree and old one respectively.BinominalTree merge(BinominalTree h1, int height, BinominalQueue bq){                if(h1 == NULL)    {        return h1;    }    if(bq->trees[height] == NULL) // if the queue don't has the B0 tree.    {                bq->trees[height] = h1;        return bq->trees[height];    }    else // otherwise, compare the new tree's height with that of old one.    {                 if(h1->value > bq->trees[height]->value) // the new should be treated as the parent of the old.        {                    innerMerge(bq->trees[height], height, h1, bq);        }        else // the old should be treated as the parent of the new.        {            innerMerge(h1, height, bq->trees[height], bq);        }    }      return h1;} BinominalTree lastChild(BinominalTree root){                    while(root->nextSibling)    {                root = root->nextSibling;    }    return root; }