https://www.cnblogs.com/chengxiao/p/6129630.html
第一个非叶子节点：arr.length/ 2 -1

  1.   heapSort(arr: number[]) {
  2.       const startIndex = Math.round(arr.length / 2) - 1 // 倒数第二层，最后一个拥有子树的节点 index
  4.       // 初始化建立最大堆
  5.       for (let i = startIndex; i >= 0; i--) {
  6.           valueSink(arr, i, arr.length)
  7.       }
  9.       // 开始排序
  10.       for (let i = arr.length - 1; i > 0; i--) {
  11.           swap(arr, 0, i) // 将堆的最大值放到堆的尾部
  12.           valueSink(arr, 0, i) // 重新将交换过来的顶部值下沉，构建新的最大堆
  13.       }
  14.       return arr
  15.   }
  18.   /**
  19.    * 为当前节点做下沉操作。比较当前值和其左右子树的值，并交换，直到其左右子树值都比它小。
  20.    * 时间复杂度: logn
  21.    * 空间复杂度: 1
  22.    * @param arr 
  23.    * @param index 下沉操作开始的节点 index
  24.    * @param len 下沉操作最沉层的最大 index
  25.    */
  26.   valueSink(arr: number[], index: number, len: number) {
  27.       while (index < len) {
  28.           const topIndex = index
  29.           const leftIndex = topIndex * 2 + 1
  30.           const rightIndex = topIndex * 2 + 2
  32.           let maxIndex = topIndex
  34.           if (leftIndex < len && arr[topIndex] < arr[leftIndex]) {
  35.               maxIndex = leftIndex
  36.           } 
  38.           if (rightIndex < len && arr[maxIndex] < arr[rightIndex]) {
  39.               maxIndex = rightIndex
  40.           }
  42.           if (maxIndex !== topIndex) {
  43.               swap(arr, topIndex, maxIndex)
  44.               index = maxIndex
  45.           } else {
  46.               break // 找到 index 的正确位置，停止位置调整
  47.           }
  48.       }
  49.       return arr
  50.   }
  52.   swap(arr: number[], i: number, j: number) {
  53.       let temp = arr[i]
  54.       arr[i] = arr[j]
  55.       arr[j] = temp
  56.   }

思路：

比较抽象，看图更容易理解。

  1. 对于数组 [16,7,3,20,17,8] 平铺转化为二叉树为：

image.png
图1-1

  1. 为了将其排序，首先要构造一个最大二叉树:

要构造最大二叉树，我们需要由下至上，对每一个节点进行下沉操作。从图1-1中可以看出，最后一层的节点都没有子节点，所以将它们跳过。从倒数第二层第一个拥有子树的节点3开始，进行下沉操作。
image.png
图2-1
如图2-1.1所示，经过一次下沉操作3已经被下沉到最底层，节点8和节点3已经构成了最大二叉树。接着为剩余的节点继续此操作，最终我们就会得到一颗最大二叉树。

  1. 将最大元素移动到数组尾部，接着再次重复下沉操作，构造最大二叉树。

image.png
图3-1
因为每次交换都只改变了一个元素的位置，所以每次交换过后，只需要再进行一次下沉操作，就可以再次得到最大二叉树。反复重复这个操作，就能够得到一个从小到大排列的数组了。

BOOM🥚
恭喜💐你，碰到了小彩蛋，讲个故事，来环节枯燥乏味的算法学习生活。

在第三次星际大战中，为了保卫人类最后的家园—🌎，你义无反顾的踏上了战场。你是一个非常优秀的地球青年，体型挺拔，长相俊秀，家境也相当殷实，你爷爷是地球防卫队总队的传奇英雄，曾经凭借一己之力，潜入敌军内部，为上一次战争的胜利立下汗马功劳。在军营里面，很多护士都对你暗送秋波，你也爱上了其中一个长相非常漂亮的护士。但是因为战争正在进行中，不想忍受生离死别的你也就并没有向她表白，甚至故意没有和她说过一句话，一直用这种冰冷的高傲与她保持着距离。
不幸的事情还是发生了，在一次抢占土星的战役中，你被H21星系的一颗爆裂弹的冲击波击中，在飞出了数百米之后就晕了过去。当你醒来时，你发现自己正躺在一所地球医院的病床上，幸运的是虽然受到如此强大的冲击，但你全身上下都并无大碍，唯独眼睛瞎了。在你忍住内心的伤痛，说服自己接受现实之后，你又发现，曾经哪些整日与你暧昧不清，大献殷勤的女人如今都已离你而去。只有一个你以前听都没听说过的女孩愿意留下来照顾你，她的声音非常的好听，对待你也特别的温柔。你心里很清楚，她的长相一定是特别的难看，但是你知道她是一个内心非常善良的女人，你告诉自己，如果将来她愿意，你一定会娶她。
不知不觉一年过去了。一天早上，你醒来时发现房间里面一个人都没有，这时你惊讶的发现，原来自己的眼睛又能看到了。你转过身，看到床边的桌子上放着一些自己常吃的药品，你随便拿起其中的一个药瓶，惊恐的发现，这是一种能够使人逐渐失明的慢性药物，而你居然每天都在吃这种药！就在你气愤之时，走廊里传来了脚步声，你立刻装作看不见的样子在床上躺好。可待到门推开的那一刻，走进来的那个女护士，竟然就是你曾经深爱着的那个漂亮的女护士。
那么，选择题来了，你还会想要娶她吗？

答：
深夜发现趣味🥚一枚。
虽然堆排序的解法还没有认真看，可是磕这我就来劲儿了。
我先盲猜一个【娶她】。等待你的下回分解。