堆排序示例及算法性能分析

【出自BD笔试题】

难度系数：★★★★☆ 被考察系数：★★★★★

题目描述：

给定一个无序整型数组，请用堆排序对数组进行升序排列。

分析与解答：

堆是一种特殊的树形数据结构，其每个结点都有一个值，通常提到的堆都是指一棵完全二叉树，根结点的值小于（或大于）两个子结点的值，同时根结点的两个子树也分别是一个堆。

堆排序是一树形选择排序，在排序过程中，将R[1，…，N]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

堆一般分为大顶堆和小顶堆两种不同的类型。对于给定n个记录的序列（r（1），r（2），…，r（n）），当且仅当满足条件（r（i）≥r（2i），i=1，2，…，n）时称之为大顶堆，此时堆顶元素必为最大值。对于给定n个记录的序列（r（1），r（2），…，r（n）），当且仅当满足条件（r（i）≤r（2i+1），i=1，2，…，n）时称之为小顶堆，此时堆顶元素必为最小值。(www.xing528.com)

堆排序的思想是对于给定的n个记录，初始时把这些记录看作为一棵顺序存储的二叉树，然后将其调整为一个大顶堆，然后将堆的最后一个元素与堆顶元素（即二叉树的根结点）进行交换后，堆的最后一个元素即为最大记录；接着将前（n-1）个元素（即不包括最大记录）重新调整为一个大顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录，重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最小记录，此时可得到一个有序序列。

堆排序主要包括两个过程：一是构建堆；二是交换堆顶元素与最后一个元素的位置。程序示例如下：

程序的输出结果如下：

27 18 14 13 1 0

算法性能分析：

堆排序方法对记录较少的文件效果一般，但对于记录较多的文件还是很有效的，其运行时间主要耗费在创建堆和反复调整堆上。堆排序即使在最坏情况下，其时间复杂度也为O（nlogn）。它是一种不稳定的排序方法。