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

using namespace std;

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

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

void HeapSort(int a[], int n){
	int k;
	// 建立 大根堆 
	for(k = n / 2; k >= 1; k--){
		HeapAdjust(a, k, n);
	}

	// 調整 （向下調整） 
	for(k = 1; k < n; k++){
		// 將 當前的堆頂 與 當前無序區(qū)的最后一個 進行交換 
		swap(a[1], a[n - k + 1]);
		
		// 1：需要調整的根結點
		// n - k：需要調整的元素個數(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;
}