Cacher is the code snippet organizer for pro developers

void swap( int arr[], int x, int y){
      int tmp = arr[x];
      arr[x] = arr[y];
      arr[y] = tmp;
}

//该操作主要用于维持堆的基本性质。
//假定以RIGHT(t)和LEFT(t)为根的子树都已经是堆，然后调整以t为根的子树，使之成为堆。
void heapify( int arr[], int size, int t){
      int left = 2*(t+1)-1;
      int right = 2*(t+1);

      //find max element
      int max = t;
      if(left < size){
            max = arr[left] > arr[max] ? left : max;
      }
      if(right < size){
            max = arr[right] > arr[max] ? right : max;
      }

      //调整后，重新维持堆
      if(max != t){
            swap(arr,t,max);
            heapify(arr,size,max);
      }
}

/**
 * 该操作主要是将数组A转化成一个大顶堆。思想是，先找到堆的最后一个非叶子节点（即为第n/2个节点），
 * 然后从该节点开始，从后往前逐个调整每个子树，使之称为堆，最终整个数组便是一个堆。
 */
void buildHeap( int arr[], int size){
      for(int i = size/2-1;i>=0;i--){
            heapify(arr,size,i);
      }
}

void heap_sort(int arr[],int size){
    buildHeap(arr,size);
    for(int i=size-1;i>0;i--){
        swap(arr,0,i);
        size--;
        heapify(arr,size,0);
    }
}