// 用于計算下標為i的節(jié)點的兩個子節(jié)點的下標值
#define LEFT(i) (2 * (i) + 1)
#define RIGHT(i) (2 * ((i) + 1))
         
/* 此函數(shù)把一顆二叉樹中以node為根的子樹變成最大堆。
 * 注意: 使用的前提條件是 node節(jié)點的左右子樹(如果存在的話)都是最大堆。
 * 這個函數(shù)是整個算法的關(guān)鍵。
 */
void max_heapify(int heap[], int heap_size, int node)
{
  // 這里先不考慮整數(shù)溢出的問題
  // 先把注意力放在主要的功能上
  // 如果數(shù)據(jù)規(guī)模夠大,int類型必然會溢出
  int l_child = LEFT(node);
  int r_child = RIGHT(node);
  int max_value = node;
 
  if (l_child < heap_size && heap[l_child] > heap[max_value])
  {
    max_value = l_child;
  }
  if (r_child < heap_size && heap[r_child] > heap[max_value])
  {
    max_value = r_child;
  }
  if (max_value != node)
  {
    swap_val(heap + node, heap + max_value);
 
    // 之后還要保證被交換的子節(jié)點構(gòu)成的子樹仍然是最大堆
    // 如果不是這個節(jié)點會繼續(xù)"下沉"，直到合適的位置
    max_heapify(heap, heap_size, max_value);
  }
}
 
/* 將一個數(shù)組構(gòu)造成最大堆
 * 自底向上的利用max_heapify函數(shù)處理
 */
void build_max_heap(int heap[], int heap_size)
{
  if (heap_size < 2)
  {
    return;
  }
  int first_leaf = heap_size >> 1;//第一個葉子節(jié)點的下標
 
  int i;
  // 從最后一個非葉子節(jié)點開始自底向上構(gòu)建，
  // 葉子節(jié)點都看作最大堆，因此可以使用max_heapify函數(shù)
  for (i = first_leaf - 1; i >= 0; i--)
  {
    max_heapify(heap, heap_size, i);
  }
}

/* heap sort 主函數(shù)
 */
void heap_sort(int heap[], int heap_size)
{
  if (heap == NULL || heap_size < 2)
  {
    return;
  }
  //構(gòu)建最大堆
  build_max_heap(heap, heap_size);
 
  int i;
  for (i = heap_size - 1; i > 0; i--)
  {
    /* 把當前樹的根節(jié)點交換到末尾
     * 相當于取出最大值，樹的規(guī)模變小。
     * 交換后的樹不是最大堆，但是根的兩顆子樹依然是最大堆
     * 滿足調(diào)用max_heapify的條件。之所以這樣交換，
     * 是因為用max_heapify處理時間復(fù)雜度較低，
     * 如果不交換而直接"取出"heap[0], 此處可能要使用
     * build_max_heap重新建立最大堆，時間復(fù)雜度較大
     */
    swap_val(heap, heap + i);
 
    heap_size--;
    //維護最大堆
    max_heapify(heap, heap_size, 0);
  }
}