|
() BuildHeap和Heapify函数的实现 因为构造初始堆必须使用到调整堆的操作先讨论Heapify的实现 ① Heapify函数思想方法 每趟排序开始前R[li]是以R[]为根的堆在R[]与R[i]交换后新的无序区R[i]中只有R[]的值发生了变化故除 R[]可能违反堆性质外其余任何结点为根的子树均是堆因此当被调整区间是R[lowhigh]时只须调整以R[low]为根的树即 可 筛选法调整堆 R[low]的左右子树(若存在)均已是堆这两棵子树的根R[low]和R[low+]分别是各自子树中关键字最大的结点若 R[low]key不小于这两个孩子结点的关键字则R[low]未违反堆性质以R[low]为根的树已是堆无须调整;否则必须将R[low]和 它的两个孩子结点中关键字较大者进行交换即R[low]与R[large](R[large]key=max(R[low]keyR[low+]key))交换交 换后又可能使结点R[large]违反堆性质同样由于该结点的两棵子树(若存在)仍然是堆故可重复上述的调整过程对以 R[large]为根的树进行调整此过程直至当前被调整的结点已满足堆性质或者该结点已是叶子为止上述过程就象过筛子一样 把较小的关键字逐层筛下去而将较大的关键字逐层选上来因此有人将此方法称为筛选法 具体的算法【参见教材】 ②BuildHeap的实现 要将初始文件R[ln]调整为一个大根堆就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆 显然只有一个结点的树是堆而在完全二叉树中所有序号 的结点都是叶子因此以这些结点为根的子树均已是堆 这样我们只需依次将以序号为 的结点作为根的子树都调整为堆即可 具体算法【参见教材】 大根堆排序实例 对于关键字序列()在建堆过程中完全二叉树及其存储结构的变化情况参见 算法分析 堆排序的时间主要由建立初始堆和反复重建堆这两部分的时间开销构成它们均是通过调用Heapify实现的 堆排序的最坏时间复杂度为O(nlgn)堆排序的平均性能较接近于最坏性能 由于建初始堆所需的比较次数较多所以堆排序不适宜于记录数较少的文件 堆排序是就地排序辅助空间为O() 它是不稳定的排序方法 |
