#include <stdio.h>
void swap(int *a,int *b) {
 int temp = *a;
 *a = *b;
 *b = temp;
}
//左右子樹都是最大堆，從上至下調(diào)整使得最大堆, root_index是要調(diào)整的樹的根節(jié)點(diǎn)，length是無序區(qū)的長度
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主遞歸，每一次將無序區(qū)最后一個(gè)元素與堆頂元素交換，將堆頂元素加入有序區(qū)，因此有序區(qū)加1,無序區(qū)減1，無序區(qū)只剩一個(gè)元素的時(shí)候遞歸終止
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);
} 
//入口函數(shù)，array是待排序的數(shù)組，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]);
 }
}