1. 概述

堆（也叫优先队列），是一棵完全二叉树，它的特点是父节点的值大于（小于）两个子节点的值（分别称为大顶堆和小顶堆），每个结点与数组中的存放位置对应。它常用于管理算法执行过程中的信息，应用场景包括堆排序，优先队列等。

2.堆排序

   堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。

 例如图9-7-4，左图是一个大顶堆，90为最大值，将90与20（末尾元素）互换，如中图所示，此时90就成了整个堆序列的最后一个元素，将20经过调整，使得除90以外的结点继续满足大顶堆定义（所有结点都大于等于其子孩子），见右图。然后再考虑将30与80互换……
       3.效率

  它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。
        在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。
        在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根结点的距离为⌊log2i⌋+1），并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。
        所以总体来说，堆排序的时间复杂度为O(nlogn)。
        空间复杂度上，它只有一个用来交换的暂存单元O(1)，也算是非常的不错。

 不过由于记录的比较与交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。
       另外，由于初始构建堆所需的比较次数较多，因此，它并不适合待排序序列个数较少的情况。