C ++程序实现最小堆
BinaryHeap是完整的二叉树，可以是MinHeap或MaxHeap。在最大二进制堆中，在二进制堆中存在的所有密钥中，根目录中的密钥必须最大。对于二叉树中的所有节点，此属性必须递归地为true。最小二进制堆类似于最小堆。
算法
对于min_heap()：
Begin
Declare function min_heap(int *a, int m, int n)
Declare j, t of the integer datatype.
Initialize t = a[m].
j = 2 * m;
while (j <= n) do
if (j < n && a[j+1] < a[j]) then
j = j + 1
if (t < a[j]) then
break
else if (t >= a[j]) then
a[j / 2] = a[j]
j = 2 * j
a[j/2] = t
return
End.对于build_minheap：
Begin
Declare function build_minheap(int *a,int n).
Declare k of the integer datatype.
for(k = n/2; k >= 1; k--)
Call function min_heap(a,k,n)
End.示例
#include <iostream>
#include <conio.h>
using namespace std;
void min_heap(int *a, int m, int n){
int j, t;
t= a[m];
j = 2 * m;
while (j <= n) {
if (j < n && a[j+1] < a[j])
j = j + 1;
if (t < a[j])
break;
else if (t >= a[j]) {
a[j/2] = a[j];
j = 2 * j;
}
}
a[j/2] = t;
return;
}
void build_minheap(int *a, int n) {
int k;
for(k = n/2; k >= 1; k--) {
min_heap(a,k,n);
}
}
int main() {
int n, i;
cout<<"enter no of elements of array\n";
cin>>n;
int a[30];
for (i = 1; i <= n; i++) {
cout<<"enter element"<<" "<<(i)<<endl;
cin>>a[i];
}
build_minheap(a, n);
cout<<"Min Heap\n";
for (i = 1; i <= n; i++) {
cout<<a[i]<<endl;
}
getch();
}输出结果
enter no of elements of array 5 enter element 1 7 enter element 2 6 enter element 3 2 enter element 4 1 enter element 5 4 Min Heap 1 4 2 6 7
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短