#include <stdio.h>
void swap(int *a,int *b) {
 int temp = *a;
 *a = *b;
 *b = temp;
}
//左右子树都是最大堆，从上至下调整使得最大堆, root_index是要调整的树的根节点，length是无序区的长度
void adjust(int array[],int root_index,int length) {
 int left_child = root_index*2+1;
 int right_child = left_child+1;
 int left_or_right = 0;
 if((left_child >= length && right_child >= length) || (left_child >= length && array[root_index] >= array[right_child]) ||
 (right_child >= length && array[root_index] >= array[left_child]) || (array[root_index] >= array[left_child] && array[root_index] >= array[right_child])){
  return;
 }
 else if (array[left_child] >= array[root_index] && (right_child >= length || array[left_child] >= array[right_child])) {
  left_or_right = 1;
 }
 else if (array[right_child] >= array[root_index] && (left_child >= length || array[right_child] >= array[left_child])) {
  left_or_right = 0;
 }
 if(left_or_right) {
  swap(&array[left_child],&array[root_index]);
  adjust(array,left_child,length);
 }
 else {
  swap(&array[right_child],&array[root_index]);
  adjust(array,right_child,length);  
 }
}
//heapsort主递归，每一次将无序区最后一个元素与堆顶元素交换，将堆顶元素加入有序区，因此有序区加1,无序区减1，无序区只剩一个元素的时候递归终止
void heapsort_main(int array[],int length,int last_index) {
 int i;
 if(last_index == 0)
  return;
 swap(&array[0],&array[last_index]);
 adjust(array,0,last_index);
 heapsort_main(array,length,last_index-1);
} 
//入口函数，array是待排序的数组，length是其长度
void heapsort(int array[],int length) {
 int i;
 for(i = length/2-1;i >= 0;i--) {
  adjust(array,i,length);
 }
 heapsort_main(array,length,length-1);
}
int main(int argc,char *argv[]) {
 int array[9] = {1,1,1,2,3,5,2,3,5};
 heapsort(array,9);
 int i;
 for(i = 0;i < 9;i++) {
  printf("%d ",array[i]);
 }
}