堆的纯C实现，按照正常工程中的标准，不透明结构体，例如 apache apr中用的都是不透明结构体

heap.c

/** @file heap.c
 * @brief 小根堆.
 * @author [email protected]
 * @date 2010-8-1
 * @version 0.1
 * @note 小根堆的源代码文件
 */
#include "heap.h"
#include <stdlib.h>  /* for malloc() */
#include <string.h>  /* for memcpy() */


/*
 *@struct
 *@brief 堆的结点.
*@note 无
 */
struct heap_t {
    int size;         /* 实际元素个数*/
    int capacity;     /* 容量大小，以元素为单位*/
    int elem_size;    /* 单个元素的大小*/
    int (*cmp)(const void*, const void*); /*元素的比较函数*/
    void *data;       /* 堆的数组*/
};

int heap_init(heap_t **h, int elem_size, 
              int (*cmp)(const void*, const void*)) {
    if(h == NULL) return ERR_NULL_POINTER;
    *h = (heap_t*)malloc(sizeof(heap_t));
    if(*h == NULL) return ERR_MALLOC_FAILED;

    (*h)->size = 0;
    (*h)->capacity = 0;
    (*h)->elem_size = elem_size;
    (*h)->cmp = cmp;
    (*h)->data = NULL;
    return SUCCESS;
}

int heap_uninit(heap_t **s) {
    if((s !=NULL) && (*s != NULL)) {
        free((*s)->data);
        free((*s));
        (*s) = NULL;
    }
    return 0;
}

/*
 * @brief 小根堆的自上向下筛选算法.
 * @param[in] h 堆对象的指针
 * @param[in] start 开始结点
 * @return 无
 * @note 无
 * @remarks 无
 */
static void heap_sift_down(const heap_t *h,int start) {
    int i = start;
    int j;
    /* data_t tmp = h->data[start]; */
    void* const tmp = malloc(h->elem_size);
    if(tmp == NULL) return /* ERR_MALLOC_FAILED */;
    memcpy(tmp, (char*)h->data + start * h->elem_size,
        h->elem_size);    
    for(j = 2 * i + 1; j < h->size; j = 2 * j + 1) {
        if(j < (h->size - 1) && 
            /* h->data[j] > h->data[j + 1] */
            h->cmp((char*)h->data + j * h->elem_size, 
            (char*)h->data + (j + 1) * h->elem_size) > 0) {
                j++; /* j 指向两子女中小者*/
        }
        /* tmp <= h->data[j] */
        if(h->cmp(tmp, (char*)h->data + j * h->elem_size) <= 0) {
            break;
        } else {
            /* h->data[i] = h->data[j]; */
            memcpy((char*)h->data + i * h->elem_size, 
                (char*)h->data + j * h->elem_size, 
                h->elem_size);
            i = j;
        }
    }
    /* h->data[i] = tmp; */
    memcpy((char*)h->data + i * h->elem_size, tmp, h->elem_size);
    free(tmp);
}

/* 
 * @brief 小根堆的自下向上筛选算法.
 * @param[in] h 堆对象的指针
 * @param[in] start 开始结点
 * @return 无
 * @note 无
 * @remarks 无
 */
static void heap_sift_up(const heap_t *h, int start) {
    int j = start;
    int i= (j - 1) / 2;
    /* data_t tmp = h->data[start]; */
    void* const tmp = malloc(h->elem_size);
    /* *tmp = h-data[start]; */
    if(tmp == NULL) return /* ERR_MALLOC_FAILED */;
    memcpy(tmp, (char*)h->data + start * h->elem_size, h->elem_size);

    while(j > 0) {
        /* h->data[i] <= tmp */
        if(h->cmp((char*)h->data + i * h->elem_size, tmp) <= 0) {
            break;
        } else {
            /* h->data[j] = h->data[i]; */
            memcpy((char*)h->data + j * h->elem_size, 
                (char*)h->data + i * h->elem_size, 
                h->elem_size);
            j = i;
            i = (i - 1) / 2;
        }
    }
    /* h->data[j] = tmp; */
    memcpy((char*)h->data + j * h->elem_size, tmp, h->elem_size);
    free(tmp);
}

int heap_create(heap_t *h, const void *arr, int n) {
    int i;

    if(h->capacity < n) {/*空间不够，重新分配*/
        free(h->data);
        h->data = malloc(n * h->elem_size);
        if(h->data == NULL) return ERR_MALLOC_FAILED;
        h->capacity = n;
    }
    /* 复制数组到堆中*/
    h->size = n;
    memcpy(h->data, arr, n * h->elem_size);

    i = (h->size - 2)/2;   /* 找最初调整位置：最后分支结点*/
    while(i >= 0) {  /* 自底向上逐步扩大形成堆*/
        heap_sift_down(h, i);
        i--;
    }
    return SUCCESS;
}

void heap_clear(heap_t *h) {
    if(h != NULL) h->size = 0;
}

bool heap_is_empty(const heap_t *h) {
    if(h != NULL) {
        return h->size == 0;
    } else {
        return false;
    }
}

bool heap_is_full(const heap_t *h) {
    if(h != NULL) {
        return h->size == h->capacity;
    } else {
        return false;
    }
}

int heap_insert(heap_t *h, const void* x) {
    if(heap_is_full(h)) { /*已经满，再分配内存*/
        void* const tmp = 
            realloc(h->data, h->capacity * h->elem_size * 2);
        if(tmp == NULL) return ERR_MALLOC_FAILED;
        h->data = tmp;
        h->capacity *= 2;
    }

    /* h->data[h->size] = x; */
    memcpy((char*)h->data + h->size * h->elem_size, 
        x, h->elem_size);
    heap_sift_up(h, h->size);
    h->size++;
    return SUCCESS;
}

int heap_remove(heap_t *h, void* x) {
    if(heap_is_empty(h)) return ERR_OTHER;

    /* *x = h->data[0]; */
    memcpy(x, h->data, h->elem_size);
    /* h->data[0] = h->data[h->size - 1]; */
    memcpy(h->data, (char*)h->data + (h->size - 1) * h->elem_size, 
        h->elem_size);
    h->size --;
    heap_sift_down(h, 0);
    return SUCCESS;
}

heap.h

/** @file heap.h
  * @brief 小根堆.
  * @author [email protected]
  * @date 2010-8-1
  * @version 0.1
  * @note 小根堆的头文件
  */
#ifndef _HEAP_H_
#define _HEAP_H_

#ifdef __cplusplus
extern "C"
{
#endif


#include "config.h"

/** 堆结构体，不透明. */
typedef struct heap_t heap_t;

/** 
  * @brief 堆的初始化.
  * @param[out] h 堆对象的二级指针
  * @param[in] elem_size 单个元素的大小
  * @param[in] cmp cmp 比较函数，小于返回-1，等于返回0，
  * 大于返回1，反过来则是大根堆
  * @return 成功返回0，失败返回错误码
  * @note 本函数会分配内存，创建一个
  * min_heap_t对象，将其地址存放在
  * h所指向的指针中
  * @remarks 无
  */
extern int heap_init(heap_t **h, int elem_size,
                     int (*cmp)(const void*, const void*));

/** 
  * @brief 释放堆所占用的内存空间.
  * @param[inout] h 堆对象的二级指针
  * @return 成功返回0，失败返回错误码
  * @note 释放栈对象本身所占用的内存
  * @remarks 无
  */
extern int heap_uninit(heap_t **s);

/** 
  * @brief 堆的建立.
  * @param[out] h 堆对象的二级指针
  * @param[in] arr 存放初始数据的数组
  * @param[in] n 数组的大小
  * @return 成功返回0，失败返回错误码
  * @note 无
  * @remarks 无
  */
extern int heap_create(heap_t *h, const void *arr, int n);

/** 
  * @brief 清空数据，但不释放内存.
  * @param[in] h 指向堆对象的指针
  * @return 无
  * @note 无
  * @remarks 无
  */
extern void heap_clear(heap_t *h);

/** 
  * @brief 判断堆是否为空.
  * @param[in] h 指向堆对象的指针
  * @return 是空，返回true，否则返回false
  * @note 无
  * @remarks 无
  */
extern bool heap_is_empty(const heap_t *h);

/** 
  * @brief 判断堆是否已满.
  * @param[in] h 指向堆对象的指针
  * @return 满，返回true，否则返回false
  * @note 无
  * @remarks 无
  */
extern bool heap_is_full(const heap_t *h);

/** 
  * @brief 在尾部插入一个元素.
  * @param[in] h 堆对象的指针
  * @param[in] x 要插入的元素
  * @return 成功返回0，失败返回错误码
  * @note 无
  * @remarks 无
  */
extern int heap_insert(heap_t *h, const void *x);

/** 
  * @brief 删除堆顶.
  * @param[in] h 堆对象的指针
  * @param[in] x 保存删除掉的元素
  * @return 成功返回0，失败返回错误码
  * @note 无
  * @remarks 无
  */
extern int heap_remove(heap_t *h, void *x);


#ifdef __cplusplus
}
#endif

#endif /* end of _HEAP_H_ */