数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究C++ 程序实现最大堆
二叉堆是完全二叉树，可以是小根堆或大根堆。在大根二叉堆中，根节点的键必须大于二叉堆中所有键的最大值。这种性质对于二叉树中的所有节点来说在递归的情况下都必须为真。小根二叉堆类似于小根堆。
算法
对于 max_heap
Begin Declare function max_heap () 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_maxheap
Begin Declare function build_maxheap(int *a,int n). Declare k of the integer datatype. for(k = n/2; k >= 1; k--) Call function max_heap(a,k,n) End.
示例
#include <iostream>
using namespace std;
void max_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_maxheap(int *a,int n) {
int k;
for(k = n/2; k >= 1; k--) {
max_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 elements"<<" "<<(i)<<endl;
cin>>a[i];
}
build_maxheap(a,n);
cout<<"Max Heap\n";
for (i = 1; i <= n; i++) {
cout<<a[i]<<endl;
}
}输出
enter no of elements of array 5 enter elements 1 7 enter elements 2 6 enter elements 3 2 enter elements 4 1 enter elements 5 4 Max Heap 7 6 2 1 4
更新于： 30-Jul-2019
13K+ 浏览次数
广告