第六章 介绍另一种排序算法————堆排序。堆排序的时间复杂度是O(ngln)，，且堆排序具有空间原址性。
第六章 堆排序 heapsort
堆排序使用一种我们称为“堆”的数据结构来进行信息管理。
堆
（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树。树上的每一个结点对应数组中的一个元素。除最底层外该树是完全充满的。而且是从左向右填充，表示堆的数组A包括两个属性：A.length(通常)给出数组元素的个数，A.heap-size表示存储在数组中的堆元素的个数。A[1..A.length]可能存有数据，但只有A[1..A.heap-size]中存放的是堆的有效元素，0≤A.heap-size≤A.length。
树的根结点是A[1],这样给定一个结点的下标i,可以计算得到PARENT(i):i/2，LEFT(i)2i，RIGHT(i)2i+1。
二叉堆可以分为两种形式：最大堆和最小堆。结点的值都需要满足堆的性质。
- 最大堆中，最大堆的性质是处理根以外的所有结点i都要满足：A[PARENT(i)]≥A[i],即某个结点的值之多与其父结点一样大。在任意子树中，该子树所包含的所有结点的值都不大于该子树根结点的值。
- 最小堆的性质是指除了根以外的所有结点i都有A[PARENT(i)]≤A[i]最小堆中的最小元素存放在根结点中。
堆排序算法中使用最大堆，构造优先队列使用最小堆。
一个堆中结点的高度：该结点到叶结点最长口岸名单路径上边的数目。故堆的高度即为根结点的高度。
堆结构上的一些基本操作的运行时间之多与树的高度成正比，即时间复杂度为O(lgn)。
维护堆的性质
MAX-HEAPIFY过程是用于为胡最大堆性质的重要过程。它的输入为一个数组A 和一个下标i。MAX-HEAPIFY通过让A[i]的值在最大堆中“逐级下降”，从而使得以下标i为根结点的子树重新遵循最大堆的性质。
