優先隊列（堆）的簡單實作執行個體

/* bin_heap.h */

#ifndef _BIN_HEAP_H
#define _BIN_HEAP_H

struct heap_struct;
typedef struct heap_struct *priority_queue;

priority_queue initialize(int max_elements);
void destroy(priority_queue h);
void make_empty(priority_queue h);
void insert(int x, priority_queue h);
int delete_min(priority_queue h);
int find_min(priority_queue h);
int is_empty(priority_queue h);
int is_full(priority_queue h);

#endif      

/* bin_heap.c */

#include "bin_heap.h"
#include <stdio.h>
#include <stdlib.h>
#include <error.h>

#define MIN_PQSIZE    5
#define MIN_DATA    -1

struct heap_struct
{
    int capacity;
    int size;
    int *elements;
};

priority_queue 
initialize(int max_elements)
{
    priority_queue h;

    if(max_elements < MIN_PQSIZE)
    {
        printf("Priority queue size is too small");
        exit(1);
    } 

    h = malloc(sizeof(struct heap_struct));
    if(h == NULL)
    {
        perror("malloc");
        exit(1);
    }
    
    h->elements = malloc(sizeof(int) * (max_elements + 1));
    if(h->elements == NULL)
    {
        perror("malloc");
        exit(1);
    }

    h->capacity = max_elements;
    h->size = 0;
    h->elements[0] = MIN_DATA;
    
    return h;
}

void 
destroy(priority_queue h)
{
    if(h != NULL)
    {
        free(h->elements);
        free(h);
    }
}

void 
make_empty(priority_queue h)
{
    h->size = 0;
}

void 
insert(int x, priority_queue h)
{
    int i;
    
    if(is_full(h))
    {
        printf("priority queue is full!!!\n");
        return;
    }

    for(i = ++(h->size); h->elements[i/2] > x; i /= 2)
    {
        h->elements[i] = h->elements[i/2];
    }
    h->elements[i] = x;
}

int 
delete_min(priority_queue h)
{
    int i, child;
    int min_element, last_element;

    if(is_empty(h))
    {
        printf("Priority queue is empty!!!\n");
        return h->elements[0];
    }

    min_element = h->elements[1];
    last_element = 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(last_element > h->elements[child])
            h->elements[i] = h->elements[child];
        else
            break;
    }
    h->elements[i] = last_element;
    return min_element;
}

int 
find_min(priority_queue h)
{
    return h->elements[1];
}

int 
is_empty(priority_queue h)
{
    return h->size == 0;
}

int 
is_full(priority_queue h)
{
    return h->size == h->capacity;
}      

/* bin_heap_test.c */

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

int
main(int argc, char **argv)
{
    int i;

    priority_queue h;
    h = initialize(100);
    insert(13, h);
    insert(21, h);
    insert(16, h);
    insert(24, h);
    insert(31, h);
    insert(19, h);
    insert(68, h);
    insert(65, h);
    insert(26, h);
    insert(32, h);
    for(i = 0; i < 10; i++)
    {
        printf("%d ", delete_min(h));
    }
    printf("\n");

    return 0;
}