在C++中，可以通過std::priority_queue來使用堆。
堆的C語言實現：
heap.c
/** @file heap.c
* @brief 堆,默認為小根堆,即堆頂為最小.
*/
#include <stdlib.h> /* for malloc() */
#include <string.h> /* for memcpy() */
typedef int heap_elem_t; // 元素的類型
/**
* @struct
* @brief 堆的結構體
*/
typedef struct heap_t
{
int size; /** 實際元素個數 */
int capacity; /** 容量,以元素為單位 */
heap_elem_t *elems; /** 堆的數組 */
int (*cmp)(const heap_elem_t*, const heap_elem_t*);
}heap_t;
/** 元素的比較函數 */
/** 基本類型(如 int, long, float, double)的比較函數 */
int cmp_int(const int *x, const int *y)
{
const int sub = *x - *y;
if(sub > 0)
{
return 1;
}
else if(sub < 0)
{
return -1;
}
else
{
return 0;
}
}
/**
* @brief 堆的初始化.
* @param[out] h 堆對象的指針
* @param[out] capacity 初始容量
* @param[in] cmp cmp 比較函數,小於返回-1,等於返回 0
* 大於返回 1,反過來則是大根堆
* @return 成功返回 0,失敗返回錯誤碼
*/
int heap_init(heap_t *h, const int capacity, int (*cmp)(const heap_elem_t*, const heap_elem_t*))
{
h->size = 0;
h->capacity = capacity;
h->elems = (heap_elem_t*)malloc(capacity * sizeof(heap_elem_t));
h->cmp = cmp;
return 0;
}
/**
* @brief 釋放堆.
* @param[inout] h 堆對象的指針
* @return 成功返回 0,失敗返回錯誤碼
*/
int heap_uninit(heap_t *h)
{
h->size = 0;
h->capacity = 0;
free(h->elems);
h->elems = NULL;
h->cmp = NULL;
return 0;
}
/**
* @brief 判斷堆是否為空.
* @param[in] h 堆對象的指針
* @return 是空,返回 1,否則返回 0
*/
int heap_empty(const heap_t *h)
{
return h->size == 0;
}
/**
* @brief 獲取元素個數.
* @param[in] s 堆對象的指針
* @return 元素個數
*/
int heap_size(const heap_t *h)
{
return h->size;
}
/*
* @brief 小根堆的自上向下篩選算法.
* @param[in] h 堆對象的指針
* @param[in] start 開始結點
* @return 無
*/
void heap_sift_down(const heap_t *h, const int start)
{
int i = start;
int j;
const heap_elem_t tmp = h->elems[start];
for(j = 2 * i + 1; j < h->size; j = 2 * j + 1)
{
if(j < (h->size - 1) && h->cmp(&(h->elems[j]), &(h->elems[j + 1])) > 0)
{
j++; /* j 指向兩子女中小者 */
}
// tmp <= h->data[j]
if(h->cmp(&tmp, &(h->elems[j])) <= 0)
{
break;
}
else
{
h->elems[i] = h->elems[j];
i = j;
}
}
h->elems[i] = tmp;
}
/*
* @brief 小根堆的自下向上篩選算法.
* @param[in] h 堆對象的指針
* @param[in] start 開始結點
* @return 無
*/
void heap_sift_up(const heap_t *h, const int start)
{
int j = start;
int i= (j - 1) / 2;
const heap_elem_t tmp = h->elems[start];
while(j > 0)
{
// h->data[i] <= tmp
if(h->cmp(&(h->elems[i]), &tmp) <= 0)
{
break;
}
else
{
h->elems[j] = h->elems[i];
j = i;
i = (i - 1) / 2;
}
}
h->elems[j] = tmp;
}
/**
* @brief 添加一個元素.
* @param[in] h 堆對象的指針
* @param[in] x 要添加的元素
* @return 無
*/
void heap_push(heap_t *h, const heap_elem_t x)
{
if(h->size == h->capacity)
{
/* 已滿,重新分配內存 */
heap_elem_t* tmp = (heap_elem_t*)realloc(h->elems, h->capacity * 2 * sizeof(heap_elem_t));
h->elems = tmp;
h->capacity *= 2;
}
h->elems[h->size] = x;
h->size++;
heap_sift_up(h, h->size - 1);
}
/**
* @brief 彈出堆頂元素.
* @param[in] h 堆對象的指針
* @return 無
*/
void heap_pop(heap_t *h)
{
h->elems[0] = h->elems[h->size - 1];
h->size --;
heap_sift_down(h, 0);
}
/**
* @brief 獲取堆頂元素.
* @param[in] h 堆對象的指針
* @return 堆頂元素
*/
heap_elem_t heap_top(const heap_t *h)
{
return h->elems[0];
}
C++ 隱式類類型轉化 Implicit Class-Type Conversions http://www.linuxidc.com/Linux/2013-01/78071.htm
C語言變長數組之剖析 http://www.linuxidc.com/Linux/2013-07/86997.htm
C語言需要注意的問題 http://www.linuxidc.com/Linux/2013-05/84301.htm
C語言位域的使用及其注意點 http://www.linuxidc.com/Linux/2013-07/87027.htm
C語言中簡單的for循環和浮點型變量 http://www.linuxidc.com/Linux/2013-08/88514.htm
