// 初始化堆
void initHeap(int a[], int len) {
 // 從完全二叉樹(shù)最后一個(gè)非子節(jié)點(diǎn)開(kāi)始
 // 在數(shù)組中第一個(gè)元素的索引是0
 // 第n個(gè)元素的左孩子為2n+1，右孩子為2n+2，
 // 最后一個(gè)非子節(jié)點(diǎn)位置在(n - 1) / 2
 for (int i = (len - 1) / 2; i >= 0; --i) {
  adjustMaxHeap(a, len, i);
 }
}
 
void adjustMaxHeap(int a[], int len, int parentNodeIndex) {
 // 若只有一個(gè)元素，那么只能是堆頂元素，也沒(méi)有必要再排序了
 if (len <= 1) {
  return;
 }
 
 // 記錄比父節(jié)點(diǎn)大的左孩子或者右孩子的索引
 int targetIndex = -1;
 
 // 獲取左、右孩子的索引
 int leftChildIndex = 2 * parentNodeIndex + 1;
 int rightChildIndex = 2 * parentNodeIndex + 2;
 
 // 沒(méi)有左孩子
 if (leftChildIndex >= len) {
  return;
 }
 
 // 有左孩子，但是沒(méi)有右孩子
 if (rightChildIndex >= len) {
  targetIndex = leftChildIndex;
 }
 // 有左孩子和右孩子
 else {
  // 取左、右孩子兩者中最大的一個(gè)
  targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex;
 }
 
 // 只有孩子比父節(jié)點(diǎn)的值還要大，才需要交換
 if (a[targetIndex] > a[parentNodeIndex]) {
  int temp = a[targetIndex];
  
  a[targetIndex] = a[parentNodeIndex];
  a[parentNodeIndex] = temp;
  
  
  // 交換完成后，有可能會(huì)導(dǎo)致a[targetIndex]結(jié)點(diǎn)所形成的子樹(shù)不滿(mǎn)足堆的條件，
  // 若不滿(mǎn)足堆的條件，則調(diào)整之使之也成為堆
  adjustMaxHeap(a, len, targetIndex);
 }
}
 
void heapSort(int a[], int len) {
 if (len <= 1) {
  return;
 }
 
 // 初始堆成無(wú)序最大堆
 initHeap(a, len);
 
 for (int i = len - 1; i > 0; --i) {
  // 將當(dāng)前堆頂元素與最后一個(gè)元素交換，保證這一趟所查找到的堆頂元素與最后一個(gè)元素交換
  // 注意：這里所說(shuō)的最后不是a[len - 1]，而是每一趟的范圍中最后一個(gè)元素
  // 為什么要加上>0判斷？每次不是說(shuō)堆頂一定是最大值嗎？沒(méi)錯(cuò)，每一趟調(diào)整后，堆頂是最大值的
  // 但是，由于len的范圍不斷地縮小，導(dǎo)致某些特殊的序列出現(xiàn)異常
  // 比如說(shuō)，5, 3, 8, 6, 4序列，當(dāng)調(diào)整i=1時(shí)，已經(jīng)調(diào)整為3,4,5,6,8序列，已經(jīng)有序了
  // 但是導(dǎo)致了a[i]與a[0]交換，由于變成了4,3,5,6,8反而變成無(wú)序了!
  if (a[0] > a[i]) {
   int temp = a[0];
   a[0] = a[i];
   a[i] = temp;
  }
  
  // 范圍變成為：
  // 0...len-1
  // 0...len-1-1
  // 0...1 // 結(jié)束
  // 其中，0是堆頂，每次都是找出在指定的范圍內(nèi)比堆頂還大的元素，然后與堆頂元素交換
  adjustMaxHeap(a, i - 1, 0);
 }
}

// 初始化堆
void initHeap(int a[], int len) {
 // 從完全二叉樹(shù)最后一個(gè)非子節(jié)點(diǎn)開(kāi)始
 // 在數(shù)組中第一個(gè)元素的索引是0
 // 第n個(gè)元素的左孩子為2n+1，右孩子為2n+2，
 // 最后一個(gè)非子節(jié)點(diǎn)位置在(n - 1) / 2
 for (int i = (len - 1) / 2; i >= 0; --i) {
  adjustMinHeap(a, len, i);
 }
}
 
void adjustMinHeap(int a[], int len, int parentNodeIndex) {
 // 若只有一個(gè)元素，那么只能是堆頂元素，也沒(méi)有必要再排序了
 if (len <= 1) {
  return;
 }
 
 // 記錄比父節(jié)點(diǎn)大的左孩子或者右孩子的索引
 int targetIndex = -1;
 
 // 獲取左、右孩子的索引
 int leftChildIndex = 2 * parentNodeIndex + 1;
 int rightChildIndex = 2 * parentNodeIndex + 2;
 
 // 沒(méi)有左孩子
 if (leftChildIndex >= len) {
  return;
 }
 
 // 有左孩子，但是沒(méi)有右孩子
 if (rightChildIndex >= len) {
  targetIndex = leftChildIndex;
 }
 // 有左孩子和右孩子
 else {
  // 取左、右孩子兩者中最上的一個(gè)
  targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex;
 }
 
 // 只有孩子比父節(jié)點(diǎn)的值還要小，才需要交換
 if (a[targetIndex] < a[parentNodeIndex]) {
  int temp = a[targetIndex];
  
  a[targetIndex] = a[parentNodeIndex];
  a[parentNodeIndex] = temp;
  
  
  // 交換完成后，有可能會(huì)導(dǎo)致a[targetIndex]結(jié)點(diǎn)所形成的子樹(shù)不滿(mǎn)足堆的條件，
  // 若不滿(mǎn)足堆的條件，則調(diào)整之使之也成為堆
  adjustMinHeap(a, len, targetIndex);
 }
}
 
void heapSort(int a[], int len) {
 if (len <= 1) {
  return;
 }
 
 // 初始堆成無(wú)序最小堆
 initHeap(a, len);
 
 for (int i = len - 1; i > 0; --i) {
  // 將當(dāng)前堆頂元素與最后一個(gè)元素交換，保證這一趟所查找到的堆頂元素與最后一個(gè)元素交換
  // 注意：這里所說(shuō)的最后不是a[len - 1]，而是每一趟的范圍中最后一個(gè)元素
  // 為什么要加上>0判斷？每次不是說(shuō)堆頂一定是最小值嗎？沒(méi)錯(cuò)，每一趟調(diào)整后，堆頂是最小值的
  // 但是，由于len的范圍不斷地縮小，導(dǎo)致某些特殊的序列出現(xiàn)異常
  // 比如說(shuō)，5, 3, 8, 6, 4序列，當(dāng)調(diào)整i=1時(shí)，已經(jīng)調(diào)整為3,4,5,6,8序列，已經(jīng)有序了
  // 但是導(dǎo)致了a[i]與a[0]交換，由于變成了4,3,5,6,8反而變成無(wú)序了!
  if (a[0] < a[i]) {
   int temp = a[0];
   a[0] = a[i];
   a[i] = temp;
  }
  
  // 范圍變成為：
  // 0...len-1
  // 0...len-1-1
  // 0...1 // 結(jié)束
  // 其中，0是堆頂，每次都是找出在指定的范圍內(nèi)比堆頂還小的元素，然后與堆頂元素交換
  adjustMinHeap(a, i - 1, 0);
 }
}

// int a[] = {5, 3, 8, 6, 4};
int a[] = {89,-7,999,-89,7,0,-888,7,-7};
heapSort(a, sizeof(a) / sizeof(int));
 
for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {
  NSLog(@"%d", a[i]);
}