資料結構
網路
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+ 瀏覽量
廣告