总结
本章介绍二叉堆。二叉堆是我们通常所说的数据结构中的“堆”之一。和之前一样，本文将首先简单介绍二叉堆的理论知识，然后给出C语言的实现。随后将分别给出C++和Java版本的实现；虽然实现语言不同，但是原理是一样的，选择其中一种来理解即可。文章如有错误或不足之处，欢迎指出！
内容
1. 堆和二叉堆简介
2. 二叉堆的图形分析
3.二叉堆的C实现（完整源代码）
4.二叉堆的C测试程序
转载请注明出处：http://www.sychzs.cn/skywang12345/p/3610187.html
更多内容：数据结构与算法系列目录
？ 二叉堆（3）Java实战
堆和二叉堆简介
堆定义
堆，这里说的堆是数据结构中的堆，而不是内存模型中的堆。堆通常可以看作一棵树，它满足以下性质：
[性质1] 堆中任何节点的值总是不大于（不小于）其所在节点的值子节点；
[性质2] 堆始终是一棵完整的树。
其中任意节点不大于其子节点的堆称为最小堆或小根堆，其中任意节点不小于其子节点的堆节点称为最大桩或Dagendui。常见的堆有二叉堆、左倾堆、倾斜堆、二项式堆、斐波那契堆等。
二叉堆的定义
二叉堆是完全二叉树或近似完全二叉树。分为两种：最大堆和最小堆。
最大堆：父节点的键值始终大于或等于任意子节点的键值；最小堆：父节点的键值总是小于或等于任何子节点的键值。示意图如下：
二叉堆一般是通过“数组”来实现的。在数组实现的二叉堆中，父节点和子节点的位置之间存在一定的关系。有时，我们将“二叉堆的第一个元素”放在数组索引0处，有时放在1处。当然，它们的本质是相同的（都是二叉堆），但实现上略有不同。
假设数组中“第一个元素”的索引为0，则父节点与子节点的位置关系如下：
(01) 索引为i的左子节点的索引为(2*i+1 );
(02) 索引为 i 的左子节点索引为 (2*i+2);
(03) 索引为 i 的父节点索引为 Floor( (i-1)/2);
假设数组中“第一个元素”的索引为1，则父节点与子节点的位置关系如下：
(01) 索引为i的左子节点的索引为(2*i);
(02) 索引为i的左子节点索引为(2*i+1);
(03) 索引为i的父节点索引为floor(i/2);
注：本文二叉堆的实现均采用“二叉堆的第一个元素位于数组索引0处”的方法！
二叉堆的图解分析
之前，我们已经了解到“最大堆”和“最小堆”是对称的。这也意味着，只知道其中之一。本节的图解分析是基于“最大堆”来介绍的。
二叉堆的核心是“添加节点”和“删除节点”。通过了解这两个算法，你就可以基本掌握二叉堆了。下面对它们进行介绍。
1。添加
假设最大堆[90,80,70,60,40,30,20,10,50]中添加85，则需要执行的步骤如下：
如上图所示，向最大堆添加数据时：先将数据添加到最大堆的末尾，然后将这个元素尽可能向上移动，直到无法再移动为止！
将 85 添加到 [90,80,70,60,40,30,20,10,50] 后，最大堆变为 [90,85,70,60,80,30,20,10 ,50, 40]。
最大堆的插入代码（C语言）
/*
* 最大堆向上调整算法（从start开始，一直到0，调整堆）
*
* 注意：在数组实现的堆中，第N个节点的左孩子索引值为(2N+1)，右孩子索引值为(2N+2)。
*
* 参数说明：
* start -- 调整点的起始位置（通常是数组最后一个元素的索引）
*/
静态 void maxheap_filterup（int开始）
{
int c = 开始； //当前节点的位置（当前）
int p = (c-1)/2; //父节点的位置
int tmp = m_heap[c]; //当前节点的大小（当前）
同时（c > 0）
{if(m_heap[p] >= tmp)
断；
否则
{
m_heap[c] = m_heap[p];
c = p；
p = (p-1)/2;
}
}
m_heap[c] = tmp;
}
/*
* 向二叉堆中插入数据
*
* 返回值：
* 0，表示成功
* -1，表示失败
*/
int maxheap_insert（int数据）
{
// 如果“堆”已满，则返回
if(m_size == m_capacity)
返回-1；
m_heap[m_size] = 数据； // 在表格末尾插入“数组”
maxheap_filterup(m_size); //向上调整堆
m_大小++； //堆实际容量+1
返回0；
}
maxheap_insert(data)的作用：将数据data添加到最大堆中。
堆满时，添加失败；否则数据将添加到最大堆的末尾。然后通过升级算法重新调整数组，使其再次成为最大堆。
2。删除
假设从最大堆[90,85,70,60,80,30,20,10,50,40]中删除90，需要执行的步骤如下：
从 [90,85,70,60,80,30,20,10,50,40] 中删除 90 后，最大堆变为 [85,80,70,60,40,30,20,10 ， 50]。
如上图所示，从最大堆中删除数据时：先删除数据，然后将最大堆中的最后一个元素插入到空的空间中；然后，将这个“空白空间”尽可能高地移动，直到剩余的数据成为最大堆。
注意：当考虑从最大堆[90,85,70,60,80,30,20,10,50,40]中删除60时，执行的步骤不能简单地将其替换为其子节点；相反，它必须考虑“被替换的树仍然必须是最大的堆”！
最大堆删除代码（C语言）
/*
* 返回二叉堆中数据的索引
*
* 返回值：
* Exists -- 返回数据在数组中的索引
* 不存在 -- -1
*/
int get_index(int数据)
{
int我=0;
对于（i=0；i）
if（数据==m_heap[i]）
返回i；
返回-1；
}
/*
* 最大堆向下调整算法
*
* 注意：在数组实现的堆中，第N个节点的左孩子索引值为(2N+1)，右孩子索引值为(2N+2)。
*
* 参数说明：* start -- 下降调整点的起始位置（一般为0，表示从第1个开始）
* end -- 直到范围（通常是数组中最后一个元素的索引）
*/
静态 void maxheap_filterdown(int开始, int 完）
{
int c = 开始； //当前节点的位置
int l = 2*c + 1； //左孩子的位置
int tmp = m_heap[c]; //当前节点的大小
同时（l <=结束）
{
// “l”是左孩子，“l+1”是右孩子
if(l < end && m_heap[l] < m_heap[l+1])
l++; // 选择左右子节点中较大的一个，即 m_heap[l+1]
if(tmp >= m_heap[l])
断； //调整结束
否则
{
m_heap[c] = m_heap[l];
c = l；
l = 2*l + 1；
}
}
m_heap[c] = tmp;
}
/** 删除最大堆中的数据
*
* 返回值：
* 0, 成功
* -1，失败
*/
int maxheap_remove(int数据)
{
int索引；
// 如果“堆”为空，则返回-1
if(m_size == 0)
返回-1；
//获取数组中数据的索引
索引 = get_index(数据);
if（索引==-1）
返回-1；
m_heap[索引] = m_heap[--m_size]; // 用最后一个元素填充
maxheap_filterdown(索引, m_size-1); //从索引位置开始从上到下调整到最大堆
返回0；
}
maxheap_remove(data)的作用：从最大堆中删除data数据。
当堆为空时，删除失败；否则，调查数据在最大堆数组中的位置。找到后，先用最后一个元素替换被删除的元素；然后通过向下调整算法重新调整数组，使其再次成为最大堆。
“示例完整代码”和“最小堆相关代码”请参考下面二叉堆的实现。
二叉堆的C实现（完整源码）
二叉堆的实现包括“最大堆”和“最小堆”。它们是对称关系；如果你理解其中一个，另一个就很容易理解了。
二叉堆（最大堆）的实现文件（max_heap.c）
1 /**
2 * 二叉堆（最大堆）
3 *
4 * @author skywang
5 * @日期 2014/03/07
6 */
7
8 #include
9 #include
10
11 #define 长度(a) ( (sizeof(a)) / (sizeof(a[0])) )
12
13 静态 int m_heap[30]; //数据
14 静态 int m_capacity=30； //总容量
15 静态 int m_size=0； // 实际容量（初始化为0）
16
17 /*
18 * 返回数据在二叉堆中的索引
19 *
20 * 返回值:
21 * Exists -- 返回数组中数据的索引
22 * 不存在 -- -1 23 */
24 int get_index(int数据)
25 {
26 int i=0；
27
28 对于（i=0；i）
29 if（数据==m_heap[i]）
30 返回；
31
32 返回 -1；
33}
34
35 /*
36 * 最大堆的后续调整算法
37 *
38 *注：在堆中实现的阵列中，第N个节点的左孩子的索引值为(2N+1)，右孩子的索引为(2N+2)。
39 *
40 * 参数说明：
41 * start -- 债务节点的起始位置(一般被为0，表示从第1个开始)
42 * end -- 肾范围（一般为数据库中最后一个元素的索引）
43 */
44 静态 void maxheap_filterdown(int) 开始，int结束）
45{ 46 int c = 开始； //当前节点的位置
47 int l = 2*c + 1； //左孩子的位置
2
49
50 同时（l <= 结束）
51 {
52 // “l”是左孩子，“l+1”是右孩子
53 if(l < end && m_heap[l] < m_heap[l+1])
54l++； // 选择左右子节点中较大的一个，即 m_heap[l+1]
55 if(tmp >= m_heap[l])
56 打破； //调整结束
57 其他
58 {
59 m_heap[c] = m_heap[l];
60 c = l；
61 l = 2*l + 1；
62 } 63 }
64 m_heap[c] = tmp;
65}
66
67 /*
68 * 删除最大堆中的数据
69 *
70 * 返回值:
71 * 0，成功
72 * -1，失败
73 */
74 int maxheap_remove（int数据）
75{
76 int索引；
77 // 如果“堆”为空，则返回-1
78 if(m_size == 0)
79 返回 -1；
80
81 // 获取数组中数据的索引
82 索引 = get_index(data);
83 if（索引==-1）
84 返回 -1；
85
86 m_heap[索引] = m_heap[--m_size]; // 用最后一个元素填充 87 maxheap_filterdown(index, m_size-1); //从索引位置开始从上到下调整到最大堆
88
89 返回0；
90}
91
92 /*
93 * 最大堆向上调整算法（从start开始向上到0，调整堆）
94 *
95 * 注：在数组实现的堆中，第N个节点的左孩子索引值为(2N+1)，右孩子索引值为(2N +2）。
96 *
97 * 参数说明：
98 * start -- 调整点的起始位置（通常是数组中最后一个元素的索引）
99 */
staticvoidmaxheap_filterup（int开始）
101{
102 int c = 开始； //当前节点的位置（当前）
103 int p = (c-1)/2; //父节点（父节点的位置）
104 int tmp = m_heap[c]; //当前节点的大小（当前）
105
106 同时（c > 0）
107 {
108 if(m_heap[p] >= tmp)109断；
110 其他
111 {
112 m_heap[c] = m_heap[p];
113 c = p；
114 p = (p-1)/2;
115}
116 }
117 m_heap[c] = tmp;
118}
119
120 /*
121 * 向二叉堆插入数据
122*
123 * 返回值：
124 * 0，表示成功
125 * -1，表示失败
126 */
127 int maxheap_insert（int数据）
128{
129 // 如果“堆”已满，则返回
130 if(m_size == m_capacity)
131返回-1；
132
133 m_heap[m_size] = 数据； //在表格末尾插入“数组”
134 maxheap_filterup(m_size); // 调整堆高
135m_size++； //堆的实际容量+1
136
137返回0；
138}
139
140 /*
141 * 打印二进制堆
142*143 * 返回值：
144 * 0，表示成功
145 * -1，表示失败
146 */
147 void maxheap_print()
148{
149int我;
150 对于 (i=0; i)
151 printf("%d ", m_heap[i]);
152}
153
154 void main()
155{
156 int a[] = {10, 40, 30, 60, 90、70、20、50、80 };
157 int i, len=LENGTH(a);
158
159 printf("==依次添加：");
160 对于（i=0；i）
161 {
162 printf("%d ", a[i]);
163 maxheap_insert(a[i]);
164 }
165
166 printf("\n== 最大堆: ");
167 maxheap_print();
168
169 i=85;
170 maxheap_insert(i);
171 printf("\n== 添加元素: %d", i);172 printf("\n== 最大堆: ");
173 maxheap_print();
174
175 i=90;
176 maxheap_remove(i);
177 printf("\n== 删除元素: %d", i);
178 printf("\n== 最大堆: ");
179 maxheap_print();
180 printf("\n");
181}
查看代码二叉堆的实现文件(min_heap.c)
1 /**
2 * 二叉堆（最小堆）
3 *
4 * @author skywang
5 * @日期 2014/03/07
6 */
7
8 #include
9 #include
10
11 #define 长度(a) ( (sizeof(a)) / (sizeof(a[0])) )
12
13 静态 int m_heap[30]; 14 静态 int m_capacity=30； //总容量
15 静态 int m_size=0； // 实际容量（初始化为0）
16
17 /*
18 * 返回数据在二叉堆中的索引
19 *
20 * 返回值:
21 * Exists -- 返回数组中数据的索引
22 * 不存在 -- -1
23 */
24 int get_index(int数据)
25 {
26 int i=0；
27
28 对于（i=0；i）
29 if（数据==m_heap[i]）
30 返回；
31
32 返回 -1；
33}
34
35 /*
36 * 最小堆向下调整算法
37 * 38 * 注：在数组实现的堆中，第N个节点的左孩子索引值为(2N+1)，右孩子索引值为(2N +2）。
39 *
40 * 参数说明：
41 * start -- 下降调整点的起始位置（一般为0，表示从第一个开始）
42 * end -- 直到范围（通常是数组中最后一个元素的索引）
43 */
44 静态 void minheap_filterdown(int) 开始，int结束）
45{
46 int c = 开始； //当前节点的位置
47 int l = 2*c + 1； //左孩子的位置
2
49
50 同时（l <= 结束）
51 {
52 // “l”是左孩子，“l+1”是右孩子
53 if(l < end && m_heap[l] > m_heap[l+1])
54l++； // 选择左右子节点中较小的一个，即 m_heap[l+1] 55 if(tmp <= m_heap[l])
56 打破； //调整结束
57 其他
58 {
59 m_heap[c] = m_heap[l];
60 c = l；
61 l = 2*l + 1；
62 }
63 }
64 m_heap[c] = tmp;
65}
66
67 /*
68 *删除最小堆中的数据
69 *
70 * 返回值：
71 * 0，成功
72 * -1，失败
73 */
74 int minheap_remove(int数据)
75{
76 int索引；
77 // 如果“堆”已空，则返回-1
78 if(m_size == 0)
79 返回 -1； 80
81 // 获取数组中数据的索引
82 索引 = get_index(data);
83 if（索引==-1）
84 返回 -1；
85
86 m_heap[索引] = m_heap[--m_size]; // 用最后一个元素填充
87 minheap_filterdown(index, m_size-1); //从索引号位置开始从上到下调整到最小堆
88
89 返回0；
90}
91
92 /*
93 * 最小堆向上调整算法（从start开始向上到0，调整堆）
94 *
95 * 注：在数组实现的堆中，第N个节点的左孩子索引值为(2N+1)，右孩子索引值为(2N +2）。
96 *
97 * 参数说明：
98 * start -- 调整点的起始位置（通常是数组中最后一个元素的索引）
99 */
100 静态 voidfilter_up（int开始）
101{102 int c = 开始； //当前节点的位置（当前）
103 int p = (c-1)/2; //父节点（父节点的位置）
104 int tmp = m_heap[c]; //当前节点的大小（当前）
105
106 同时（c > 0）
107 {
108 if(m_heap[p] <= tmp)
109断；
110 其他
111 {
112 m_heap[c] = m_heap[p];
113 c = p；
114 p = (p-1)/2;
115}
116 }
117 m_heap[c] = tmp;
118}
119
120 /*
121 * 向二叉堆插入数据
122*
123 * 返回值：
124 * 0，表示成功
125 * -1，表示失败
126 */
127 int minheap_insert（int数据）
128{
129 // 如果“堆”已满，则返回
130 if(m_size == m_capacity)131返回-1；
132
133 m_heap[m_size] = 数据； //在表格末尾插入“数组”
134filter_up(m_size); //调整堆高
135m_size++； //堆的实际容量+1
136
137返回0；
138}
139
140 /*
141 * 打印二进制堆
142*
143 * 返回值：
144 * 0，表示成功
145 * -1，表示失败
146 */
147 void minheap_print()
148{
149int我;
150 对于 (i=0; i)
151 printf("%d ", m_heap[i]);
152}
153
154 void main()
155{
156 int a[] = {80, 40, 30, 60, 90、70、10、50、20 };
157 int i, len=LENGTH(a);
158
159 printf("==依次添加：");
160 对于（i=0；i）
161 {162 printf("%d ", a[i]);
163 minheap_insert(a[i]);
164 }
165
166 printf("\n== 最小堆: ");
167 minheap_print();
168
169 i=15;
170 minheap_insert(i);
171 printf("\n== 添加元素: %d", i);
172 printf("\n== 最小堆: ");
173 minheap_print();
174
175 i=10;
176 minheap_remove(i);
177 printf("\n== 删除元素: %d", i);
178 printf("\n== 最小堆: ");
179 minheap_print();
180 printf("\n");
181}
查看代码二叉堆的C测试程序
测试程序已包含在相应的实现文件中，这里不再赘述。
最大堆（max_heap.c）的运行结果：
按顺序添加：
== 最大堆： 90 80 70 60 40 30 20 10== 添加元素：85
== 最大堆： 90 85 70 60 80 30 20 10 50 40
==删除元素：90
== 最大堆： 85 80 70 60 40 30 20 10 50
最小堆（min_heap.c）的运行结果：
== 按顺序添加： 80 40 30 60 90 70 10 50 20
== 最小堆： 10 20 30 50 90 70 40 8060
== 添加元素：15
== 最小堆： 10 15 30 50 20 70 40 806090
==删除元素：10
== 最小堆： 15 20 30 50 90 70 40 8060
PS。 二叉堆是“堆排序”的理论基石。以后讲解算法时，我们会讲解“堆排序”。理解了“二叉堆”之后，“堆排序”就会很简单了。
