数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律学使用 C++ 代码实现最小堆
二叉堆是一种完全二叉树，要么是最小堆，要么是最大堆。在最大二叉堆中，根处的键必须是二叉堆中所有键中的最大值。对于二叉树中的所有节点，此属性必须递归为 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
更新于：30-Jul-2019
11K+ 浏览量
广告