#include <iostream>
using namespace std;
class suanfa {
public:
/*将a[i]为根节点的子树生成最大堆!*/
void heapify(int* a, int i);
/*获取父节点,在这里没用*/
int parent(int i);
/*获取左子树,数组序号*/
int left(int i);
/*获取右子树,数组序号*/
int right(int i);
/*交换2个值*/
void swap(int *a ,int i, int j);
/*暂时先不用--日后再用*/
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 << "我被析构了" << endl;
}
void suanfa::heapify(int* a, int i){
int l = left(i);
int r = right(i);
int largest = 0;//以a[i]为根节点的子树的最大值的数组下标
int size = 10;//heapsize 这里=数组的大小
/**获取该子树最大下标*/
if (l <= size - 1 && a[l] > a[i]) {
largest = l;
}else {
largest = r;
}
if (r <= size - 1 && a[r] > a[largest]) {
largest = r;
}
/*如果根节点不是改子数组最大值,则进行交换*/
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的子数组是最大堆.
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;
}