#include<stdio.h>
#include<stdlib.h>

using namespace std;

void swap(int &a, int &b){
	int temp = a;
	a = b;
	b = temp;
} 

// end：元素個(gè)數(shù) 
void HeapAdjust(int r[], int k, int end){
	int i = k; // 根節(jié)點(diǎn) 
	int j = 2 * k; // 左孩子節(jié)點(diǎn) 
	while(j <= end){
		// j < end：當(dāng)前該節(jié)點(diǎn) 有右孩子
		// r[j] > r[j + 1]：左子樹(shù)值 > 右子樹(shù)值 
		if(j < end && r[j] > r[j + 1]){
			// j 指向 左右子樹(shù)值較小者：右子樹(shù) 
			j++; 
		}
		// 根結(jié)點(diǎn)值 > 孩子結(jié)點(diǎn)值 
		if(r[i] > r[j]){
			swap(r[i], r[j]);
		}
		// 向下進(jìn)行調(diào)整 
		i = j;
		j = 2 * i;
	}
}

void HeapSort(int a[], int n){
	int k;
	// 建立 大根堆 
	for(k = n / 2; k >= 1; k--){
		HeapAdjust(a, k, n);
	}
	// 調(diào)整 （向下調(diào)整） 
	for(k = 1; k < n; k++){
		// 將 當(dāng)前的堆頂 與 當(dāng)前無(wú)序區(qū)的最后一個(gè) 進(jìn)行交換 
		swap(a[1], a[n - k + 1]);
		
		// 1：需要調(diào)整的根結(jié)點(diǎn)
		// n - k：需要調(diào)整的元素個(gè)數(shù) 	
		HeapAdjust(a, 1, n - k);
	}
} 

int main(){
	// a[0] 未使用 
	int a[7] = {0, 28, 25, 16, 36, 18, 32};
	
	for(int i = 1; i < 7; i++){
		printf("%d	", a[i]);
	}
	printf("\n");
	
	HeapSort(a, 6);
	
	for(int i = 1; i < 7; i++){
		printf("%d	", a[i]);
	}
	
	return 0;
}