总结
上一章介绍了堆和二叉堆的基本概念，并通过C语言实现了二叉堆。本章是二叉堆的C++实现。
目录
1。二叉堆简介
2.二叉堆图文分析
3.二叉堆的C++实现（完整源代码）
4.二叉堆C++测试程序
转载请注明出处：http://www.sychzs.cn/skywang12345/p/3610382.html
更多内容：数据结构与算法系列目录
(01)二叉堆(1)图形文本分析与C语言实现
(02)二叉堆(2)C++实现
(03)二叉堆(3)Java实战
二叉堆简介
二叉堆是完全二叉树或近似完全二叉树。根据数据的排列方式可以分为两种：最大堆和最小堆。
最大堆：父节点的键值始终大于或等于任意子节点的键值；最小堆：父节点的键值总是小于或等于任何子节点的键值。示意图如下：
二叉堆一般是通过“数组”来实现的。在数组实现的二叉堆中，父节点和子节点的位置之间存在一定的关系。有时，我们将“二叉堆的第一个元素”放在数组索引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。基本定义
模板<类 T>
类最大堆{
私人：
T *mHeap； //数据
int m容量； //总容量
int mSize; // 实际容量
私人：
//最大堆向下调整算法
void过滤（int开始，int结束）；
//最大堆向上调整算法（从start开始向上到0，调整堆）void过滤（int启动）；
公共：
最大堆（）；
MaxHeap(int容量);
~MaxHeap();
// 返回二叉堆中数据的索引
int getIndex(T 数据);
//删除最大堆中的数据
int删除（T数据）；
//将数据插入二进制堆
int插入（T数据）；
//打印二进制堆
void print();
};
MaxHeap是最大堆对应的类。 它包含的核心内容是“添加”和“删除”。通过了解这两个算法，你就可以基本掌握二叉堆了。下面对它们进行介绍。
2。添加
假设最大堆[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 -- 调整点的起始位置（通常是数组最后一个元素的索引）
*/
模板 <类 T>
void MaxHeap::filterup(int开始)
{
int c = 开始； //当前节点的位置（当前）
int p = (c-1)/2; //父节点的位置
T tmp = mHeap[c]; //当前节点的大小（当前）
同时（c > 0）
{
if(mHeap[p] >= tmp)
断；
否则
{
mHeap[c] = mHeap[p];
c = p；
p = (p-1)/2;
}
}
mHeap[c] = tmp;
}
/*
* 向二叉堆中插入数据
*
* 返回值：
* 0，表示成功
* -1，表示失败
*/
模板 <类 T>
intMaxHeap::插入(T数据)
{// 如果“堆”已满，则返回
if(m尺寸==m容量)
返回-1；
mHeap[mSize] = 数据； // 在表格末尾插入“数组”
过滤（mSize）； //向上调整堆
m尺寸++； //堆的实际容量+1
返回0；
}
insert(data)的作用：将数据data添加到最大堆中。 堆满时，添加失败；否则，数据将添加到最大堆的末尾。然后通过升级算法重新调整数组，使其再次成为最大堆。
3。删除
假设从最大堆[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++语言）
/*
* 最大堆向下调整算法
*
* 注意：在数组实现的堆中，第N个节点的左孩子索引值为(2N+1)，右孩子索引值为(2N+2)。
*
* 参数说明：
* start -- 下降调整点的起始位置（一般为0，表示从第1个开始）
* end -- 直到范围（通常是数组中最后一个元素的索引）
*/
模板 <类 T>
voidmaxheap:: filterdown（int开始，intend）
{
int c = 开始； //当前节点的位置
int l = 2*c + 1； // 左孩子的位置
T tmp = mHeap[c]; //当前节点的大小
同时（l <=结束）
{
// “l”是左孩子，“l+1”是右孩子
if(l < end && mHeap[l] < mHeap[l+1])
l++； // 选择两个孩子中较大的一个，即 mHeap[l+1]
if(tmp >= mHeap[l])断； //调整完成
否则
{
mHeap[c] = mHeap[l];
c = l；
l = 2*l + 1；
}
}
mHeap[c] = tmp;
}
/*
* 删除最大堆中的数据
*
* 返回值：
* 0, 成功
* -1，失败
*/
模板 <类 T>
intMaxHeap::删除（T数据）
{
int索引；
// 如果“堆”为空，则返回-1
if(mSize == 0)
返回-1；
//获取数组中数据的索引
索引 = getIndex(data);
if（索引==-1）
返回-1；
mHeap[索引] = mHeap[--mSize]; // 用最后一个元素填充
filterdown(index, mSize-1); //从索引位置开始从上到下调整到最大堆
返回0；
}
二叉堆的C++实现（完整源码）
二叉堆的实现包括“最大堆”和“最小堆”。
二叉堆（最大堆）实现文件（MaxHeap.cpp）
1 /**
2 * 二叉堆（最大堆）
3 *
4 * @author skywang
5 * @日期 2014/03/07
6 */
7
8 #include
9 #include
10 使用 命名空间 std；
11
12 模板 <类 T>
13 类最大堆{
14 私人：
15 T *mHeap； //数据
16 int m容量； // 总容量
17 int m尺寸； // 实际容量
18
19私人：
20 //最大堆向下调整算法 21 void 过滤（int开始， in t结束）；
22 //最大堆的向上调整算法（从start开始向上到0，调整堆）
23 void 过滤（int开始）；
24 公共：
25 MaxHeap();
26 MaxHeap(int容量);
27 ~MaxHeap();
28
29 // 返回数据在二叉堆中的索引
30 int getIndex(T 数据);
31 // 删除最大堆中的数据
32 int 删除（T 数据）；
33 // 将数据插入二进制堆
34 int 插入（T 数据）；
35 // 打印二进制堆
36 void print();
37}；
38
39 /*
40 * 构造函数
41 */ 42 模板 <类 T>
43MaxHeap::MaxHeap()
44 {
45 新（这个）MaxHeap（30）；
46 }
47
48 模板 <类 T>
49MaxHeap::MaxHeap(int容量)
50 {
51 m尺寸 = 0；
52 m容量=容量；
53 mHeap = 新 T[mCapacity];
54 }
55 /*
56 * 解析构造函数
57 */
58 模板 <类 T>
59MaxHeap::~MaxHeap()
60 {
61 m尺寸 = 0；
62 m容量 = 0；
63 删除[] mHeap;
64 }
65
66 /*
67 * 返回数据在二叉堆中的索引
68 *
69 * 返回值： 70 * Exists -- 返回数组中数据的索引
71 * 不存在 -- -1
72 */
73 模板 <类 T>
74 int MaxHeap::getIndex(T 数据)
75 {
我我++）
77 if（数据==mHeap[i]）
78 返回 i；
79
80 返回 -1；
81 }
82
83 /*
84 * 最大堆向下调整算法
85 *
86 * 注：数组实现的堆中，第N个节点的左孩子索引值为(2N+1)，右孩子索引值为(2N +2）。
87 *
88 * 参数说明：
89 * start -- 下降调整点的起始位置（一般为0，表示从第一个开始）
90 * end -- 直到范围（通常是数组中最后一个元素的索引）
91 */
92 模板 <类 T> 93 void MaxHeap::filterdown(int) 开始，int结束）
94 {
95 int c = 开始； //当前节点的位置
96 int l = 2*c + 1； // 左孩子的位置
97 T tmp = mHeap[c]; //当前节点的大小
98
99 同时（l <= 结束）
100 {
101 // “l”是左孩子，“l+1”是右孩子
102 if(l < end && mHeap[l] < mHeap[l+1])
103l++; // 选择左右子节点中较大的一个，即 mHeap[l+1]
104 if(tmp >= mHeap[l])
105断； //调整完成
106 其他
107 {
108 mHeap[c] = mHeap[l];
109 c = l；
110 l = 2*l + 1；
111}
112 }113 mHeap[c] = tmp;
114}
115
116 /*
117 * 删除最大堆中的数据
118 *
119 * 返回值：
120 * 0，成功
121 * -1，失败
122 */
123模板<类T>
124 int MaxHeap::删除（T 数据）
125{
126 int 索引；
127 // 如果“堆”为空，则返回-1
128 if(mSize == 0)
129返回-1；
130
131 // 获取数组中数据的索引
132索引 = getIndex(data);
133 if（索引==-1）
134返回-1；
135
136 mHeap[索引] = mHeap[--mSize]; // 用最后一个元素填充
137 filterdown(index, mSize-1); //从索引位置开始从上到下调整到最大堆
138
139返回0；
140}
141
142 /*
143 * 最大堆向上调整算法（从start开始向上到0，调整堆）
144 *
145 * 注：数组实现的堆中，第N个节点的左孩子索引值为(2N+1)，右孩子索引值为(2N+2)。146 *
147 * 参数说明：
148 * start -- 调整点的起始位置（通常是数组中最后一个元素的索引）
149 */
150模板<类T>
133 void MaxHeap::filterup(int开始)
152{
153 int c = 开始； //当前节点的位置（当前）
154 int p = (c-1)/2; //父节点（父节点的位置）
155 T tmp = mHeap[c]; //当前节点的大小（当前）
156
157 同时（c > 0）
158 {
159 if(mHeap[p] >= tmp)
160断；
161其他
162 {
163 mHeap[c] = mHeap[p];
164 c = p；
165 p = (p-1)/2;
166 }
167}
168 mHeap[c] = tmp;
169}
170
171 /*
172 * 向二叉堆中插入数据
173 *
174 * 返回值：
175 * 0，表示成功176 * -1，表示失败
177 */
178模板<类T>
179 int MaxHeap::插入（T 数据）
180{
181 // 如果“堆”已满，则返回
182 if（m尺寸 == m容量）
183返回-1；
184
185 mHeap[mSize] = 数据； // 在表格末尾插入“数组”
186 过滤（mSize）； // 调整堆高
187mSize++； //堆的实际容量+1
188
189返回0；
190}
191
192 /*
193 * 打印二进制堆
194 *
195 * 返回值：
196 * 0，表示成功
197 * -1，表示失败
198 */
199模板<类T>
200 void MaxHeap::print()
201{
202 用于 (int i=0; i)
203计算<< mHeap[i] << “”;
204}
205
206 int main()
207{208 int a[] = {10, 40, 30, 60, 90、70、20、50、80 };
209 int i, len=(尺寸(a)) / (尺寸(一个[0]））;
210MaxHeap<int>*树=新MaxHeap<int>();
211
212 cout << "== 依次添加: ";
213 对于（i=0；i）
214 {
215 cout << a[i] <<" ";
216树->insert(a[i]);
217}
218
219 cout << "\n== 最堆: ";
220树->print();
221
222 i=85;
223树->插入(i);
224 cout << "\n==添加元素: " << i;
225 cout << "\n== 最大堆: ";
226树->print();
227
228 i=90;
229树->删除(i);
230 cout << "\n== 删除元素: " << i;
231 cout << "\n== 最大堆: ";232树->print();
233 cout << endl;
234
235返回0；
236 }
查看代码二叉堆（最小堆）实现文件（MinHeap.cpp）
1 /**
2 * 二叉堆（最小堆）
3 *
4 * @author skywang
5 * @日期 2014/03/07
6 */
7
8 #include
9 #include
10 使用 命名空间 std；
11
12 模板 <类 T>
13 类 最小堆{
14 私人：
15 T *mHeap； //数据
16 int m容量； // 总容量
17 int m尺寸； // 实际容量 18
19私人：
20 //最小堆向下调整算法
21 void 过滤（int开始， in t结束）；
22 // 最小堆向上调整算法（从start开始向上到0，调整堆）
23 void 过滤（int开始）；
24 公共：
25 MinHeap();
26 MinHeap(int容量);
27 ~MinHeap();
28
29 // 返回数据在二叉堆中的索引
30 int getIndex(T 数据);
31 // 删除最小堆中的数据
32 int 删除（T 数据）；
33 // 将数据插入二进制堆
34 int 插入（T 数据）；
35 // 打印二进制堆
36 void print();
37}； 38
39 /*
40 * 构造函数
41 */
42 模板 <类 T>
43MinHeap::MinHeap()
44 {
45 新（这个）MinHeap（30）；
46 }
47
48 模板 <类 T>
49 MinHeap::MinHeap(int容量)
50 {
51 m尺寸 = 0；
52 m容量=容量；
53 mHeap = 新 T[mCapacity];
54 }
55 /*
56 *
57 */
58 模板 <类 T>
59MinHeap::~MinHeap()
60 {
61 m尺寸 = 0；
62 m容量 = 0；
63 删除[] mHeap;
64 }
65
66 /* 67 * 返回二叉堆中数据的索引
68 *
69 * 返回值：
70 * Exists -- 返回数组中数据的索引
71 * 不存在 -- -1
72 */
73 模板 <类 T>
74 int MinHeap::getIndex(T 数据)
75 {
我我++）
77 if（数据==mHeap[i]）
78 返回 i；
79
80 返回 -1；
81 }
82
83 /*
84 * 最小堆向下调整算法
85 *
86 * 注：数组实现的堆中，第N个节点的左孩子索引值为(2N+1)，右孩子索引值为(2N +2）。
87 *
88 * 参数说明：
89 * start -- 下降调整点的起始位置（一般为0，表示从第一个开始）
90 * end -- 直到范围（通常是数组中最后一个元素的索引）
91 */ 92 模板 <类 T>
93 void MinHeap::filterdown(int) 开始，int结束）
94 {
95 int c = 开始； //当前节点的位置
96 int l = 2*c + 1； // 左孩子的位置
97 T tmp = mHeap[c]; //当前节点的大小
98
99 同时（l <= 结束）
100 {
101 // “l”是左孩子，“l+1”是右孩子
102 if(l < end && mHeap[l] > mHeap[l+1])
103l++； // 选择左右子节点中较小的一个，即 mHeap[l+1]
104 if(tmp <= mHeap[l])
105断； //调整完成
106 其他
107 {
108 mHeap[c] = mHeap[l];
109 c = l；
110 l = 2*l + 1；111}
112 }
113 mHeap[c] = tmp;
114}
115
116 /*
117 * 删除最小堆中的数据
118 *
119 * 返回值：
120 * 0，成功
121 * -1，失败
122 */
123模板<类T>
124 intMinHeap::删除（T数据）
125{
126 int 索引；
127 // 如果“堆”为空，则返回-1
128 if(mSize == 0)
129返回-1；
130
131 // 获取数组中数据的索引
132索引 = getIndex(data);
133 if（索引==-1）
134返回-1；
135
136 mHeap[索引] = mHeap[--mSize]; // 用最后一个元素填充
137 filterdown(index, mSize-1); //从索引号位置开始从上到下调整到最小堆
138
139返回0；
140}
141
142 /*
143 * 最小堆向上调整算法（从start开始向上到0，调整堆）
144 *145 * 注：数组实现的堆中，第N个节点的左孩子索引值为(2N+1)，右孩子索引值为(2N+2)。
146 *
147 * 参数说明：
148 * start -- 调整点的起始位置（通常是数组中最后一个元素的索引）
149 */
150模板<类T>
151 void MinHeap::filterup(int开始)
152{
153 int c = 开始； //当前节点的位置（当前）
154 int p = (c-1)/2; //父节点（父节点的位置）
155 T tmp = mHeap[c]; //当前节点的大小（当前）
156
157 同时（c > 0）
158 {
159 if(mHeap[p] <= tmp)
160断；
161其他
162 {
163 mHeap[c] = mHeap[p];
164 c = p；
165 p = (p-1)/2;
166 }
167}
168 mHeap[c] = tmp;
169}
170
171/*
172 * 向二叉堆中插入数据173 *
174 * 返回值：
175 * 0，表示成功
176 * -1，表示失败
177 */
178模板<类T>
179 intMinHeap::插入（T数据）
180{
181 // 如果“堆”已满，则返回
182 if（m尺寸 == m容量）
183返回-1；
184
185 mHeap[mSize] = 数据； // 在表格末尾插入“数组”
186 过滤（mSize）； // 调整堆高
187mSize++； //堆的实际容量+1
188
189返回0；
190}
191
192 /*
193 * 打印二进制堆
194 *
195 * 返回值：
196 * 0，表示成功
197 * -1，表示失败
198 */
199模板<类T>
200 void MinHeap::print()
201{
202 用于 (int i=0; i)
203计算<< mHeap[i] << “”;
204}
205206 int main()
207{
208 int a[] = {80, 40, 30, 60, 90、70、10、50、20 };
209 int i, len=(尺寸(a)) / (尺寸(一个[0]））;
210MinHeap<int>*树=新MinHeap<int>();
211
212 cout << "== 依次添加: ";
213 对于（i=0；i）
214 {
215 cout << a[i] <<" ";
216树->insert(a[i]);
217}
218
219 cout << "\n== 最小堆: ";
220树->print();
221
222 i=15;
223树->插入(i);
224 cout << "\n==添加元素: " << i;
225 cout << "\n== 最小的堆: ";
226树->print();
227
228 i=10;
229树->删除(i);
230 cout << "\n== 删除元素: " << i;231 cout << "\n== 最小堆：";
232树->print();
233 cout << endl;
234
235返回0；
236 }
查看代码C++二进制堆测试程序
测试程序已包含在相应的实现文件（MaxHeap.cpp）中。下面仅列出程序运行结果。
最大堆（MaxHeap.cpp）的运行结果：
== 按顺序添加： 10 40 30 60 90 70 205080
== 最大堆： 90 80 70 60 40 30 20 1050
==添加元素：85
== 最大堆： 90 85 70 60 80 30 20 105040
==删除元素：90
== 最大堆： 85 80 70 60 40 30 20 1050
最小堆（MinHeap.cpp）的运行结果：
== 按顺序添加： 80 40 30 60 90 70 105020
== 最小堆： 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。二叉堆是“堆排序”的理论基石。 以后讲解算法时，我们会讲解“堆排序”。理解了“二叉堆”之后，“堆排序”就会很简单了。
