在C++中，可以通過std::priority_queue來使用堆。
堆的C語言實現：
heap.c
1 /** @file heap.c
2 * @brief 堆,默認為小根堆,即堆頂為最小.
3 */
4 #include <stdlib.h> /* for malloc() */
5 #include <string.h> /* for memcpy() */
6 typedef int heap_elem_t; // 元素的類型
7
8 /**
9 * @struct
10 * @brief 堆的結構體
11 */
12 typedef struct heap_t
13 {
14 int size; /** 實際元素個數 */
15 int capacity; /** 容量,以元素為單位 */
16 heap_elem_t *elems; /** 堆的數組 */
17 int (*cmp)(const heap_elem_t*, const heap_elem_t*);
18 }heap_t;
19
20 /** 元素的比較函數 */
21 /** 基本類型(如 int, long, float, double)的比較函數 */
22 int cmp_int(const int *x, const int *y)
23 {
24 const int sub = *x - *y;
25 if(sub > 0)
26 {
27 return 1;
28 }
29 else if(sub < 0)
30 {
31 return -1;
32 }
33 else
34 {
35 return 0;
36 }
37 }
38
39 /**
40 * @brief 堆的初始化.
41 * @param[out] h 堆對象的指針
42 * @param[out] capacity 初始容量
43 * @param[in] cmp cmp 比較函數,小於返回-1,等於返回 0
44 * 大於返回 1,反過來則是大根堆
45 * @return 成功返回 0,失敗返回錯誤碼
46 */
47 int heap_init(heap_t *h, const int capacity, int (*cmp)(const heap_elem_t*, const heap_elem_t*))
48 {
49 h->size = 0;
50 h->capacity = capacity;
51 h->elems = (heap_elem_t*)malloc(capacity * sizeof(heap_elem_t));
52 h->cmp = cmp;
53 return 0;
54 }
55
56 /**
57 * @brief 釋放堆.
58 * @param[inout] h 堆對象的指針
59 * @return 成功返回 0,失敗返回錯誤碼
60 */
61 int heap_uninit(heap_t *h)
62 {
63 h->size = 0;
64 h->capacity = 0;
65 free(h->elems);
66 h->elems = NULL;
67 h->cmp = NULL;
68 return 0;
69 }
70
71 /**
72 * @brief 判斷堆是否為空.
73 * @param[in] h 堆對象的指針
74 * @return 是空,返回 1,否則返回 0
75 */
76 int heap_empty(const heap_t *h)
77 {
78 return h->size == 0;
79 }
80
81 /**
82 * @brief 獲取元素個數.
83 * @param[in] s 堆對象的指針
84 * @return 元素個數
85 */
86 int heap_size(const heap_t *h)
87 {
88 return h->size;
89 }
90
91 /*
92 * @brief 小根堆的自上向下篩選算法.
93 * @param[in] h 堆對象的指針
94 * @param[in] start 開始結點
95 * @return 無
96 */
97 void heap_sift_down(const heap_t *h, const int start)
98 {
99 int i = start;
100 int j;
101 const heap_elem_t tmp = h->elems[start];
102 for(j = 2 * i + 1; j < h->size; j = 2 * j + 1)
103 {
104 if(j < (h->size - 1) && h->cmp(&(h->elems[j]), &(h->elems[j + 1])) > 0)
105 {
106 j++; /* j 指向兩子女中小者 */
107 }
108 // tmp <= h->data[j]
109 if(h->cmp(&tmp, &(h->elems[j])) <= 0)
110 {
111 break;
112 }
113 else
114 {
115 h->elems[i] = h->elems[j];
116 i = j;
117 }
118 }
119 h->elems[i] = tmp;
120 }
121
122 /*
123 * @brief 小根堆的自下向上篩選算法.
124 * @param[in] h 堆對象的指針
125 * @param[in] start 開始結點
126 * @return 無
127 */
128 void heap_sift_up(const heap_t *h, const int start)
129 {
130 int j = start;
131 int i= (j - 1) / 2;
132 const heap_elem_t tmp = h->elems[start];
133
134 while(j > 0)
135 {
136 // h->data[i] <= tmp
137 if(h->cmp(&(h->elems[i]), &tmp) <= 0)
138 {
139 break;
140 }
141 else
142 {
143 h->elems[j] = h->elems[i];
144 j = i;
145 i = (i - 1) / 2;
146 }
147 }
148 h->elems[j] = tmp;
149 }
150
151 /**
152 * @brief 添加一個元素.
153 * @param[in] h 堆對象的指針
154 * @param[in] x 要添加的元素
155 * @return 無
156 */
157 void heap_push(heap_t *h, const heap_elem_t x)
158 {
159 if(h->size == h->capacity)
160 {
161 /* 已滿,重新分配內存 */
162 heap_elem_t* tmp = (heap_elem_t*)realloc(h->elems, h->capacity * 2 * sizeof(heap_elem_t));
163 h->elems = tmp;
164 h->capacity *= 2;
165 }
166 h->elems[h->size] = x;
167 h->size++;
168 heap_sift_up(h, h->size - 1);
169 }
170
171 /**
172 * @brief 彈出堆頂元素.
173 * @param[in] h 堆對象的指針
174 * @return 無
175 */
176 void heap_pop(heap_t *h)
177 {
178 h->elems[0] = h->elems[h->size - 1];
179 h->size --;
180 heap_sift_down(h, 0);
181 }
182
183 /**
184 * @brief 獲取堆頂元素.
185 * @param[in] h 堆對象的指針
186 * @return 堆頂元素
187 */
188 heap_elem_t heap_top(const heap_t *h)
189 {
190 return h->elems[0];
191 }
