对元素序列如何进行堆排序

对元素序列如何进行堆排序


就此题讲一下堆排序是怎样进行的

首先说一个知识点,就是用数组操作二叉树(把堆看成二叉树容易理解)

一个数组a[n],a[0]不考虑舍弃,a[1]为根节点那么,a[i]的两个孩子节点就是a[2i]和a[2i+1] (不理解的话自己做下实验),好了那么k[i]<=k[2i]且k[i]<=k[2i+1](1<=i<= n）,当然,这是小根堆,大根堆则换成>=号.
用小根堆排序的基本思想(用小根堆排序其排序结果是递减有序的,大根堆排序是递增有序)
先将初始数组k[1..n]建成一个小根堆
此堆为初始的无序区再将最小的记录k[1]（即堆顶）和无序区的最后一个记录k[n]交换,由此得到新的无序区k[1..n-1]和有序区k[n],且满足k[1..n-1]<=k[n]
由于交换后新的根节点k[1]可能违反堆性质,故应将当前无序区k[1..n-1]调整为堆.然后再次对k[1..n-1]进行上面重复的操作.直到无序区只有一个元素为止.那么排序也就算结束了.
这就是堆排序的思想
你的题目上说的是原始数据构成的初始堆
7  3 5 9 1 12 实际上是这样的
          7
      3      5
 9   1        12
5和12比较不变,9,1和3比较调换1和3的位置1,5和7比较调换1和7的位置则变成这样
          1
      7      5
 9   3        12
还不满足小根堆继续比较9,3和7比较替换3和7的位置3,5和1比较不用换
          1
      3      5
 9   7        12
满足小根堆了,所以初始堆为1,3,5,9,7,12(选B)
还不懂的话这里有个动态模拟过程

再问： 堆排序是不是就是根是最小的，就是同一分支自下而上逐渐减小？左右分支不需要比较么 还有做一道选择题，说堆是——A完全二叉树 B线性表 C二叉排序树 D平衡二叉树 那既然堆是树形结构，怎么它又是线性表呢
再答： n个元素序列{k1,k2...ki...kn},当且仅当满足下列关系时称之为堆： (ki = k2i+1), (i = 1,2,3,4...n/2) 堆是一个线性表是线性结构不是树形结构,只是它这样的性质刚好可以用一棵二叉树了描述所以很多地方都把它当成二叉树来看待 小根堆排序就是根最小,然后每次都把第一个元素和当前堆的最后一个元素交换,那么最后结果肯定是有序的比如这样 {k1,k2...ki...kn}交换k1和kn,就变成这样{kn,k3...,kn-1,k1},然后把k1前面的重新调整为小根堆,假设为 {ki1,ki2...kin,k1},那么再次调换ki这个小根堆的ki1和kin就变成这样{kin,ki2...ki1,k1},这里k1一定整个序列最大的,ki1是倒数第二大的,也就是说这两个数已经是有序的了,如此循环直到有序的数前面只剩下一个数的时候,那么最后的序列也就是排好序的