堆排序的堆是怎么建立的?
发布网友
共4个回答
热心网友
堆排序，也叫二叉堆排序。
完全二叉树：
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位置的比较，直到这两个位置的数都比它小。
热心网友
先将元素按顺序插入数组 形成完全二叉树 然后按照定义对二叉树内元素即数组元素进行调整 初始化堆 使数组内元素满足 (以小根堆为例)a[x]<=a[x*2]且a[x]<=a[x*2+1] 如有什么不懂得 还可以问我
热心网友
根据堆的概念，使用一维数组即可建立，关键在于建立堆得算法追问请教一下，我关键就是想问，堆排序的堆是怎么建立的
热心网友
堆排序确实比较难理解，不知你用的是哪本书？
