优先队列--C语言实现

/* binomial.h */

#ifndef _BINOMIAL_H_
#define _BINOMIAL_H_

typedef long element_type;

#define INFINITY    (30000L)

#define MAX_TREES    (14)
#define CAPACITY    (16383)

struct bin_node;
typedef struct bin_node *bin_tree;
struct collection;
typedef struct collection *bin_queue;

#endif
/* end */
/**********************************************************************************************************/

/* binomial.c
 * 实现了优先队列插入、合并、删除最小单元等操作
 * [e-mail]
 */

#include
#include

#include "binomial.h"
#include "fatal.h"

typedef struct bin_node *pos;

struct bin_node
{
    element_type    element;
    pos    left_child;
    pos    next_sibling;
};

struct collection
{
    int    cur_size;
    bin_tree    trees[ MAX_TREES ];
};

/*
合并两个优先队列，通过后h1返回新的优先队列指针
*/
static bin_queue
bq_merge( bin_queue h1, bin_queue h2 );

static int
is_empty( bin_queue h )
{
    return h->cur_size == 0;
}

static int
is_full( bin_queue h )
{
    return h->cur_size == CAPACITY;
}

/*
初始化一个空优先队列
返回空优先队列的指针
*/
static bin_queue
initialize( void )
{
    bin_queue h;
    int i;

    h = malloc( sizeof( struct collection ) );
    if ( h == NULL )
        Error("Out of space!");

    h->cur_size = 0;
    for ( i = 0; i < MAX_TREES; i++ ){
        h->trees[ i ] = NULL;
    }

    return h;
}

/* 删除一颗二项树 */
static void
destroy_tree( bin_tree t )
{
    if ( t != NULL ){
        destroy_tree( t->left_child );
        destroy_tree( t->next_sibling );
        free( t );
    }
}

/*
static void
destroy_bq( bin_queue h )
{
    int i;

    for ( i = 0; i < MAX_TREES; i++ ){
        destroy_tree( h->trees[ i ] );
        h->trees[ i ] = NULL;
    }
}
*/

/*
清除优先队列中所有的节点
*/
static bin_queue
make_empty( bin_queue h )
{
    int i;

    /*destroy_bq( h );*/
    for ( i = 0; i < MAX_TREES; i++ ){
        destroy_tree( h->trees[ i ] );
        h->trees[ i ] = NULL;
    }
    h->cur_size = 0;
    return h;
}

/*
插入一个节点
*/
static bin_queue
insert( element_type item, bin_queue h )
{
    bin_tree    new_node;
    bin_queue    bq_one_item;

    new_node = malloc( sizeof( struct bin_node ) );
    if ( new_node == NULL )
        Error("Out of space!");

    new_node->left_child = new_node->next_sibling = NULL;
    new_node->element = item;

    /* 先构造一个新优先队列放置新节点，然后与原来的优先队列合并 */
    bq_one_item = initialize( );
    bq_one_item->cur_size = 1;
    bq_one_item->trees[ 0 ] = new_node;

    return bq_merge( h, bq_one_item );
}

/*
删除优先队列中最小值的节点
*/
static element_type
delete_min( bin_queue h )
{
    int i, j;
    int min_tree;    /* 最小值所在的那棵树的节点号 */

    bin_queue    delete_queue;
    pos            delete_tree, old_root;
    element_type    min_item;

    if ( is_empty( h ) )
        Error("Empty binomial queue!");

    /* 先找到最小值所在的树 */
    min_item = INFINITY;
    for ( i = 0; i < MAX_TREES; i++ ){
        if ( h->trees[ i ] &&
            h->trees[ i ]->element < min_item ){
            min_item = h->trees[ i ]->element;
            min_tree = i;
        }
    }
   
    /* 先删除根节点 */
    delete_tree = h->trees[ min_tree ];
    old_root = delete_tree;
    delete_tree = delete_tree->left_child;
    free( old_root );

    /* 然后用这颗没有根节点的树构造一个新的优先队列 */
    delete_queue = initialize( );
    delete_queue->cur_size = ( 1 << min_tree ) - 1;
    for ( j = min_tree - 1; j >= 0; j-- ){
        delete_queue->trees[ j ] = delete_tree;
        delete_tree = delete_tree->next_sibling;
        delete_queue->trees[ j ]->next_sibling = NULL;
    }

    /* 原来的优先队列中的一颗树已经剥离出来了，需要调整一下 */
    h->trees[ min_tree ] = NULL;
    h->cur_size -= delete_queue->cur_size + 1;

    /* 将新生的优先队列与原来的优先队列合并 */
    bq_merge( h, delete_queue );

    return min_item;
}

static element_type
find_min( bin_queue h )
{
    int i;
    element_type min_item;

    if ( is_empty( h ) )
        Error("Empty binomial queue!");

    min_item = INFINITY;
    for ( i = 0; i < MAX_TREES; i++ ){
        if ( h->trees[ i ] &&
            h->trees[ i ]->element < min_item )
            min_item = h->trees[ i ]->element;
    }
   
    return min_item;
}

/* 合并两颗二项树，通过t1返回新树的指针*/
static bin_tree
combine_trees( bin_tree t1, bin_tree t2 )
{
    if ( t1->element > t2->element )
        return combine_trees( t2, t1 );

    /*
    t1根节点值小于t2根节点值
    让t2成为t1的left_child、t1原来的left_child成为t2的next_sibling
    */
    t2->next_sibling = t1->left_child;
    t1->left_child = t2;

    return t1;
}

/*
合并两个优先队列，通过后h1返回新的优先队列指针
*/
static bin_queue
bq_merge( bin_queue h1, bin_queue h2 )
{
    bin_tree t1, t2, carry = NULL;
    int i, j;

    if ( h1->cur_size + h2->cur_size > CAPACITY )
        Error("Merge would exceed capacity!");

    h1->cur_size += h2->cur_size;
    for ( i = 0, j = 1; j <= h1->cur_size; i++, j *= 2 ){
        t1 = h1->trees[ i ];
        t2 = h2->trees[ i ];

        switch ( !!t1 + 2 * !!t2 + 4 * !!carry ){
        case 0:    /* No trees*/
        case 1: /* Only h1 */
            break;

        case 2: /* Only h2 */
            h1->trees[ i ] = t2;
            h2->trees[ i ] = NULL;
            break;
        case 4: /* Only carray */
            h1->trees[ i ] = carry;
            carry = NULL;
            break;
        case 3: /* h1 and h2 */
            carry = combine_trees( t1, t2 );
            h1->trees[ i ] = h2->trees[ i ] = NULL;
            break;
        case 5: /* h1 and carry */
            carry = combine_trees( t1, carry );
            h1->trees[ i ] = NULL;
            break;
        case 6: /* h2 and carry */
            carry = combine_trees( t2, carry );
            h2->trees[ i ] = NULL;
            break;
        case 7:    /* All three */
            h1->trees[ i ] = carry;
            carry = combine_trees( t1, t2 );
            h2->trees[ i ] = NULL;
            break;
        default:
            break;
        }
    }

    return h1;
}

/************    The next is test functions    ***************/
#define get_array_size(array)    ( sizeof(array) / sizeof(array[0]) )

void
test_binomial( void )
{
    int i;
    element_type min_item;
    bin_queue h;
    element_type datas[16];

    for ( i = 0; i < get_array_size(datas); i++ ){
        /* rand()是个“伪”随机数函数*/
        datas[i] = rand() % 100;
    }

    h = initialize( );
    if ( h == NULL )
        Error("Binary queue initialize fail!");

    /* test for build binomial */
    for ( i = 0; i < get_array_size( datas ); i++ ){
        h = insert( datas[ i ], h );
    }

    /* test for find_min */
    min_item = find_min( h );

    /* test for delete_min */
    min_item = delete_min( h );
    min_item = delete_min( h );

    while ( 1 );

    return;
}

/* end */