Priority Queue实现代码

heap.c

#include <stdlib.h>
#include <stdio.h>
#include "heap.h"

PriorityQueue pq_init(int capacity)
{
        PriorityQueue H;

        H=(PriorityQueue )malloc(sizeof(struct HeapStruct));

        H->hp=(int *)malloc((capacity+1)*sizeof(int));

        H->capacity=capacity;
        H->size=0;

        H->hp[0]=-1;

        return H;
}

void pq_destroy(PriorityQueue H)
{
        free(H->hp);
        free(H);
}

int pq_isfull(PriorityQueue H)
{
        return H->size == H->capacity;
}

int pq_isempty(PriorityQueue H)
{
        return (H->size == 0);
}

void pq_insert(PriorityQueue H, int e)
{
        int i;
        if(pq_isfull(H)) {
                printf("is full,can not insert\n");
                return;
        }
        for(i=(H->size+1);e<(H->hp[i/2]);i=i/2)
                H->hp[i]=H->hp[i/2];
        H->hp[i]=e;
        H->size++;
}

int del_min(PriorityQueue H)
{
        if(pq_isempty(H)) {
                printf("is empty,can not del_min\n");
                return H->hp[0];
        }
        int min=H->hp[1];
        int last=H->hp[H->size--];
        int i;
        int child;
        for(i=1;i*2 <= H->size;i=child) {
                child=i*2;
                if(child != H->size && H->hp[child] > H->hp[child+1])
                        child++;
                if(last < H->hp[child])
                        break;
                H->hp[i]=H->hp[child];
        }
        H->hp[i]=last;
        return min;
}

void build_heap(PriorityQueue H, int *p, int k)
{
        int i;
        for(i=1;i<k+1;i++)
                H->hp[i]=p[i-1];
        H->size=k;
        for(i=k/2;i>0;i--) {
                int j,child;
                for(j=i;j*2 <= H->size;j=child) {
                        child=2*j;
                        if(child != H->size && H->hp[child] > H->hp[child+1])
                                child++;
                        if(H->hp[j] > H->hp[child]) {
                                int temp=H->hp[j];
                                H->hp[j]=H->hp[child];
                                H->hp[child]=temp;
                        }

                }
        }
}

heap.h

struct HeapStruct {
        int capacity;
        int size;
        int *hp;
};

typedef struct HeapStruct* PriorityQueue;

PriorityQueue pq_init(int capacity);
void pq_destroy(PriorityQueue H);
void pq_insert(PriorityQueue H, int e);
int del_min(PriorityQueue H);
int pq_isfull(PriorityQueue H);
int pq_isempty(PriorityQueue H);
void build_heap(PriorityQueue H, int *p, int k);

main.c

#include <stdio.h>
#include "heap.h"

void print_pq(PriorityQueue H)
{
        int size=H->size;
        int i;
        for(i=1;i<size+1;i++)
        {
                printf("%d\t",H->hp[i]);
        }
        printf("\n");
}

int main(void)
{
        int array[8]={12,21,24,17,9,4,34,45};
        int res;
        PriorityQueue H;

        H=pq_init(50);
        build_heap(H,array,8);
        print_pq(H);

        pq_insert(H,33);
        pq_insert(H,6);
        print_pq(H);

        res=del_min(H);
        printf("min:%d\n",res);
        print_pq(H);

        pq_destroy(H);

        return 0;

}