func initHeap(inout a: [Int]) {
 for var i = (a.count - 1) / 2; i >= 0; --i {
  adjustMaxHeap(&a, len: a.count, parentNodeIndex: i)
 }
}
 
func adjustMaxHeap(inout a: [Int], len: Int, parentNodeIndex: Int) {
 // 如果len <= 0，说明已经无序区已经缩小到0
 guard len > 1 else {
  return
 }
 
 // 父结点的左、右孩子的索引
 let leftChildIndex = 2 * parentNodeIndex + 1
 
 // 如果连左孩子都没有， 一定没有右孩子，说明已经不用再往下了
 guard leftChildIndex < len else {
  return
 }
 
 let rightChildIndex = 2 * parentNodeIndex + 2
 
 // 用于记录需要与父结点交换的孩子的索引
 var targetIndex = -1
 
 // 若没有右孩子，但有左孩子，只能选择左孩子
 if rightChildIndex > len {
  targetIndex = leftChildIndex
 } else {
  // 左、右孩子都有，则需要找出最大的一个
  targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex
 }
 
 // 只有孩子比父结点还要大，再需要交换
 if a[targetIndex] > a[parentNodeIndex] {
  let temp = a[targetIndex]
  
  a[targetIndex] = a[parentNodeIndex]
  a[parentNodeIndex] = temp
  
  // 由于交换后，可能会破坏掉新的子树堆的性质，因此需要调整以a[targetIndex]为父结点的子树，使之满足堆的性质
  adjustMaxHeap(&a, len: len, parentNodeIndex: targetIndex)
 }
}
 
func maxHeapSort(inout a: [Int]) {
 guard a.count > 1 else {
  return
 }
 
 initHeap(&a)
 
 for var i = a.count - 1; i > 0; --i {
  // 每一趟都将堆顶交换到指定范围内的最后一个位置
  if a[0] > a[i] {
   let temp = a[0]
   
   a[0] = a[i]
   a[i] = temp
  }
  print(a)
  print(i - 1)
  // 有序区长度+1，而无序区长度-1，继续缩小无序区，所以i-1
  // 堆顶永远是在0号位置，所以父结点调整从堆顶开始就可以了
  adjustMaxHeap(&a, len: i - 1, parentNodeIndex: 0)
  print(a)
 }
}

func initHeap(inout a: [Int]) {
 for var i = (a.count - 1) / 2; i >= 0; --i {
  adjustMinHeap(&a, len: a.count, parentNodeIndex: i)
 }
}
 
func adjustMinHeap(inout a: [Int], len: Int, parentNodeIndex: Int) {
 // 如果len <= 0，说明已经无序区已经缩小到0
 guard len > 1 else {
  return
 }
 
 // 父结点的左、右孩子的索引
 let leftChildIndex = 2 * parentNodeIndex + 1
 
 // 如果连左孩子都没有， 一定没有右孩子，说明已经不用再往下了
 guard leftChildIndex < len else {
  return
 }
 
 let rightChildIndex = 2 * parentNodeIndex + 2
 
 // 用于记录需要与父结点交换的孩子的索引
 var targetIndex = -1
 
 // 若没有右孩子，但有左孩子，只能选择左孩子
 if rightChildIndex > len {
  targetIndex = leftChildIndex
 } else {
  // 左、右孩子都有，则需要找出最大的一个
  targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex
 }
 
 // 只有孩子比父结点还要大，再需要交换
 if a[targetIndex] < a[parentNodeIndex] {
  let temp = a[targetIndex]
  
  a[targetIndex] = a[parentNodeIndex]
  a[parentNodeIndex] = temp
  
  // 由于交换后，可能会破坏掉新的子树堆的性质，因此需要调整以a[targetIndex]为父结点的子树，使之满足堆的性质
  adjustMinHeap(&a, len: len, parentNodeIndex: targetIndex)
 }
}
 
func minHeapSort(inout a: [Int]) {
 guard a.count > 1 else {
  return
 }
 
 initHeap(&a)
 
 for var i = a.count - 1; i > 0; --i {
  // 每一趟都将堆顶交换到指定范围内的最后一个位置
  if a[0] < a[i] {
   let temp = a[0]
   
   a[0] = a[i]
   a[i] = temp
  } else {
    return // 可以直接退出了，因为已经全部有序了
  }
  
  // 有序区长度+1，而无序区长度-1，继续缩小无序区，所以i-1
  // 堆顶永远是在0号位置，所以父结点调整从堆顶开始就可以了
  adjustMinHeap(&a, len: i - 1, parentNodeIndex: 0)
 }
}

var arr = [5, 3, 8, 6, 4]
//var arr = [89,-7,999,-89,7,0,-888,7,-7]
maxHeapSort(&arr)
 
print(arr)
 
// 打印日志如下：
[4, 6, 5, 3, 8]
3
[6, 4, 5, 3, 8]
 
[3, 4, 5, 6, 8]
2
[5, 4, 3, 6, 8]
 
[3, 4, 5, 6, 8]
1
[3, 4, 5, 6, 8]
 
[3, 4, 5, 6, 8]
0
[3, 4, 5, 6, 8]
 
[3, 4, 5, 6, 8]