#include <iostream>
using namespace std;
class suanfa {
public:
/*將a[i]為根節(jié)點(diǎn)的子樹生成最大堆!*/
void heapify(int* a, int i);
/*獲取父節(jié)點(diǎn),在這里沒用*/
int parent(int i);
/*獲取左子樹,數(shù)組序號(hào)*/
int left(int i);
/*獲取右子樹,數(shù)組序號(hào)*/
int right(int i);
/*交換2個(gè)值*/
void swap(int *a ,int i, int j);
/*暫時(shí)先不用--日后再用*/
void max_heapify(int* a, int heapsize);
~suanfa();
};
int suanfa::left(int i){
return 2*i + 1;
}
int suanfa::right(int i){
return 2*i+2;
}
int suanfa::parent(int i){
return i/2;
}
suanfa::~suanfa(){
//delete [] a;
//m_array = NULL;
cout << "我被析構(gòu)了" << endl;
}
void suanfa::heapify(int* a, int i){
int l = left(i);
int r = right(i);
int largest = 0;//以a[i]為根節(jié)點(diǎn)的子樹的最大值的數(shù)組下標(biāo)
int size = 10;//heapsize 這里=數(shù)組的大小
/**獲取該子樹最大下標(biāo)*/
if (l <= size - 1 && a[l] > a[i]) {
largest = l;
}else {
largest = r;
}
if (r <= size - 1 && a[r] > a[largest]) {
largest = r;
}
/*如果根節(jié)點(diǎn)不是改子數(shù)組最大值,則進(jìn)行交換*/
if (a[i] < a[largest]) {
swap(a, i, largest);
heapify(a, largest);
}
}
void suanfa::swap(int* a, int i, int j){
int key = a[i];
a[i] = a[j];
a[j] = key;
}
void suanfa::max_heapify(int* a, int heapsize){
//j->(heapsize-1)/2的子數(shù)組是最大堆.
for(int j = (heapsize - 1) / 2; j >=0; --j)
{
heapify(a,j);
}
}
int main () {
suanfa sf;
int a[] = {16,4,10,14,7,9,3,2,8,1};
int size = sizeof a / sizeof a[0];
for(int j = (size - 1) / 2; j >=0; --j)
{
sf.heapify(a,j);
}
for (int i=0; i<size; i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}