1
Andiry 2016-02-11 10:16:36 +08:00 via Android 1
堆是层次有序的
|
2
aheadlead 2016-02-11 10:45:43 +08:00
比如说你有个 n 个数的大顶堆(就是任何一个节点比它的子节点要大)
把根(也就是整个堆里面最大的数)取出来,也就是删除(删除的操作为 O(log n) ) 上面这个操作重复 n-1 次,就完成了排序 |
3
wwttc 2016-02-11 11:31:41 +08:00 1
1. 堆(二叉堆)是一个数组,可以看成一个近似的完全二叉树,树中每一个结点对应数组中的一个元素。二叉堆有两种形式:最大堆和最小堆。在最大堆中,除了根结点之外的所有结点的值小于等于其父节点的值,因此,堆中最大的元素存放在根结点中,并且在任一子树中,该子树所包含的所有结点的值都不大于该子树根结点的值。最小堆的组织方式正好相反。因此,每次只是保证根结点处是当前剩余节点的最大(或最小)的。
2. 堆排序的过程如下: ①利用 BUILD-MAX-HEAP 将输入数组 A[1..n]建成一个最大堆,其中 n = A.length ; ②将数组最大元素所在的 A[1]位置的值与 A[n]位置的值进行交换,然后从堆中去掉结点 n ; ③在新的根结点 1 可能会违背最大堆的性质,因此需要利用 MAX-HEAPIFY 进行调整; ④不断重复 2,3 步,直到堆中只剩下一个元素,此时排序完成。 3. 因为使用了堆这个数据结构,所以就叫堆排序。 |