Question

已知关键字序列（56，30，71，29，97，83，74，64，76，48），采用堆排序算法进行递增排序，给出前5各趟排

解：
初始堆：97 76 83 64 48 71 74 56 29 30
第一趟：83 76 74 64 48 71 30 56 29 97
第二趟：76 64 74 56 48 71 30 29 83 97
第三趟：74 64 71 56 48 29 30 76 83 97
第四趟：71 64 30 56 48 29 74 76 83 97
第五趟：64 56 30 29 48 71 74 76 83 97

以上是答案
是不是先建大顶堆 ？ 可是如果是大顶堆 为什么答案里的初始序列是97 76 83 64 48 71 74 56 29 30 最后两个数不是应该 30 29 这样吗？

然后排序过程 稍微说下哈 谢谢啦 一直弄不懂堆排序 T T

Answer 1

堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。 　　（1）用大根堆排序的基本思想 　　① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区 　　② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key 　　③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 　　…… 　　直到无序区只有一个元素为止。 　　（2）大根堆排序算法的基本操作： 　　① 初始化操作：将R[1..n]构造为初始堆； 　　② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。 　　注意： 　　①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。 　　②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止
特点......................见参考材料