算法4 阅读手记

第二章

2.4

大多数在下沉排序期间重新插入堆的元素会被直接加入到堆底。Floyd 在 1964 年观察发现，我们正好可以通过免去检查元素是否到达正确位置来节省时间。在下沉中总是直接提升较大的子结点直至到达堆底，然后再使元素上浮到正确的位置。这个想法几乎可以将比较次数减少一半——接近了归并排序所需的比较次数（随机数组）。这种方法需要额外的空间，因此在实际应用中只有当比较操作代价较高时才有用（例如，当我们在将字符串或者其他键值较长类型的元素进行排序时）。

按：

这里在阅读的过程中一开始有点理解不清。后来想明白了，先看这一句话“大多数在下沉排序期间重新插入堆的元素会被直接加入到堆底。”，所谓堆底，对应数组中就是最右边界的位置，然后是为什么这句话是对的呢？因为本来我们取的就是上一个状体的堆底的元素，根据堆的性质，这个数据应该比较小，所以，它最终应该在的位置还是应该还是在堆的最底层。

然后，所以这里的方法就是我们在删除头结点(根结点)之后，不必将堆底的元素给提上来，而是一步一步把下一层的结点中较大的结点给提上来，最后一直这样操作到堆的最后一层，这种方法显然也能够达到最终的目的，并且更加省事儿。