Question

堆排序的堆是怎么建立的？

看了堆排序的概念，但是还是不是很清楚。
概念上说，每次都先建堆，然后形成完全二叉树，然后提出最大的根节点，重新建堆。
不过我对完全二叉树的概念不是很清楚。还有这个建堆到底是根据什么建的，没明白，还请指教。

Answer 1

堆排序，也叫二叉堆排序。
完全二叉树：
1、左右子树的节点数满足 Ln/Rn=1
2、左右子树高度满足 Rh+1>=Lh>=Rh
3、子节点值统一比父节点大（小）。

最大堆：2叉树的所有子节点都比父节点小。所以根节点是最大的。
最小堆：2叉树的所有子节点都比父节点大。所以根节点是最小的。

建堆：假设最多有N个数据。开辟一段用来存这N个数据的空间。根节点位置为0。其子节点位置为1、2。所有子节点位置与父节点的位置（k）关系：k，2k+1，2k+2。 假设已经有了n个数据，那么新数据自然放在n位（因为位置是从0开始），定义一个函数 shift_up() 用来调整新数据。它的功能是：将新数据与 (n-1)/2 位置的数据（新数据的父节点）比较，如果比父节点大，那么就交换，继续比较，直到它比父节点小。

重新建堆： 当取数据时，就是将根节点取出来。因为根节点是最大的，所以自然还要将其所有子节点进行调整，以保证剩下的数据的根节点是最大的。方法是：将最后一个数放到根节点位置（因为根节点取出后，根节点就空了），然后调用 shift_down()函数将其与1、2位置的数比较，如果比它大，则交换，然后继续与2k+1，2k+2位置的比较，直到这两个位置的数都比它小。

Answer 2

先将元素按顺序插入数组 形成完全二叉树 然后按照定义对二叉树内元素即数组元素进行调整 初始化堆 使数组内元素满足 (以小根堆为例)a[x]<=a[x*2]且a[x]<=a[x*2+1] 如有什么不懂得 还可以问我

Answer 3

根据堆的概念，使用一维数组即可建立，关键在于建立堆得算法

追问

请教一下，我关键就是想问，堆排序的堆是怎么建立的

Answer 4

堆排序确实比较难理解，不知你用的是哪本书？