C语言实现优先队列

 优先队列(堆)是允许至少下列两种 *** 作的数据结构:Insert(插入),它的工作显而易见的,以及DeleteMin(删除最小者),它的工作是找出、返回和删除优先队列中最小的元素。

 如同大多数数据结构那样,有时可能要添加一些 *** 作,但这些添加的 *** 作属于扩展的 *** 作,而不属于图1所描述的基本模型。

 使 *** 作被快速执行的性质是堆序(heap order)性,由于我们想要快速地找到最小元因此最小元应该在根上。应用这个逻辑我们得到堆序性质。在一个堆中,对于每一个节点X,X的父亲中的关键字小于(或等于)X中的关键字(这种堆叫做最小堆),根节点除外(它没有父亲)。图2中左边的树是一个堆,但是,右边的树则不是(虚线表示堆序性质被破坏)。

 无论从概念上还是实际上考虑,执行这两种所要求的 *** 作都是容易的,只需始终保持堆序性质。

 Insert(插入):插入 *** 作一般使用的策略叫做上滤(percolate up):新元素在堆中上滤直到找出正确的位置(设堆为H,待插入的元素为X,首先在size+1的位置建立一个空穴,然后比较X和空穴的父亲的大小,把“大的父亲”换下来,以此推进,最后把X放到合适的位置)。

 DeleteMin(删除最小元):与插入“上滤”相对应,采用一种“下滤”的策略,就是逐层推进,把较小的儿子换上来,这里面有个小的问题在具体算法实现上要注意,设堆的最后一个元素是L,在推进到倒数第二层时,将导致最后一层的某个孩子被换上去而产生一个洞,这时候为了保持堆的结构,必须把最后一个元素运过去补上,此时就存在一个问题,如果L比那个孩子小的话就不能保证堆序的性质了,所以在程序中要加一个if语句来进行这个边界条件的处理,对于一个完整的程序,算法是重要的一方面,而对算法边界问题的处理则是更重要的一方面。

#include 
#include 
#include 

struct HeapStruct
{
    int Capacity;
    int Size;
    int *Elements;
};

typedef struct HeapStruct *pri_queue;

pri_queue pri_queue_init(int MaxElements);
void destroy_queue(pri_queue H);
void make_prique_empty(pri_queue H);
void push_pri_queue(int X, pri_queue H);
int pop_pri_queue(pri_queue H);
int find_que_min(pri_queue H);
int is_queue_empty(pri_queue H);
int is_queue_full(pri_queue H);
void printf_pri_queue(pri_queue H);

#define MinPQSize (10)
#define MinData (-32767)

pri_queue pri_queue_init(int MaxElements)
{
    pri_queue H;

    if (MaxElements < MinPQSize)
        printf("\nPriority queue size is too small!\n");

    H = malloc(sizeof(struct HeapStruct));
    if (H == NULL)
        printf("\nOut of space!!!\n");

    /* Allocate the array plus one extra for sentinel */
    H->Elements = malloc((MaxElements + 1) * sizeof(int));
    if (H->Elements == NULL)
        printf("Out of space!!!\n");

    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData;

    return H;
}

/* H->Elements[ 0 ] is a sentinel */
void push_pri_queue(int X, pri_queue H)
{
    int i;

    if (is_queue_full(H))
    {
        printf("Priority queue is full\n");
        return;
    }
    for (i = ++H->Size; H->Elements[i / 2] > X; i /= 2) /* The new element is percolated up the heap  */
        H->Elements[i] = H->Elements[i / 2];            /* until the correct location is found */
    H->Elements[i] = X;
}

int pop_pri_queue(pri_queue H)
{
    int i, Child;
    int MinElement, LastElement;

    if (is_queue_empty(H))
    {
        printf("Priority queue is empty!\n");
        return H->Elements[0];
    }
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];

    for (i = 1; i * 2 <= H->Size; i = Child)
    {
        /* Find smaller child */
        Child = i * 2;
        if (Child != H->Size && H->Elements[Child + 1] < H->Elements[Child])
            Child++;

        /* Percolate one level */
        if (LastElement > H->Elements[Child])
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }
    H->Elements[i] = LastElement;
    return MinElement;
}

void make_prique_empty(pri_queue H)
{
    H->Size = 0;
}

int find_que_min(pri_queue H)
{
    if (!is_queue_empty(H))
        return H->Elements[1];
    printf("Priority Queue is Empty");
    return H->Elements[0];
}

int is_queue_empty(pri_queue H)
{
    return H->Size == 0;
}

int is_queue_full(pri_queue H)
{
    return H->Size == H->Capacity;
}

void destroy_queue(pri_queue H)
{
    free(H->Elements);
    free(H);
}

int main(int argc, char **argv)
{
    pri_queue H = pri_queue_init(50);
    int ar[] = {32, 21, 16, 24, 31, 19, 68, 65, 26, 13};
    int i;

    for (i = 0; i < 11; i++)
        push_pri_queue(ar[i], H);

    printf_pri_queue(H);

    printf("\n测试pop_pri_queue():\n");
    for (i = 0; i < 10; i++)
    {
        printf("%d ", pop_pri_queue(H));
    }
    printf("\n\n");

    return 0;
}

void printf_pri_queue(pri_queue H)
{
    int i = 0;

    printf("\n直接输出优先队列的内容：\n");

    for (i = 1; i < H->Size; i++)
        printf("%d ", H->Elements[i]);

    printf("\n\n");
}