Tag Archives: 堆排序

算法技术手册 – 排序 – 堆排序

堆排序依赖于上午写道的构建堆和调整堆。

基本思想:
(1)首先执行BuildHeap(以最大堆为例),则arr[0]已经是最大元素了,如果我们要按照从小到大排序,那么它应该被放在arr[n-1]上,于是,我们swap arr[0]和arr[n-1]。
(2)类似的,我们让i从n-1到0,依次执行调整堆,AdjustHeap(i,n),每次调整完成后,堆顶部一定是最大元素,正好把他换到i-2上。
上述的思路和选择排序是不是非常相似!

改进:
调整堆实际用到了递归方法,而其实它是[……]

继续阅读

算法技术手册 – 排序 – 堆排序 – 调整堆和构造堆

堆的下标相关:

对于大小为n的堆(0~n-1)中的一个元素idx
(1)左孩子:idx*2 + 1
(2)右孩子:idx*2 + 2
(3)父亲结点:(idx-1)/2
(4)最大(右下)的非叶子结点:n/2-1
特别注意(4)区别于(3),为什么呢?最后一个结点为n-1,那么它的父亲结点肯定是最后一个非叶子结点。即(n-1-1)/2 = n/2 – 1,都是下标搞的麻烦是吧!

目的:通过n/2-1次调整堆,可以构造一个堆。

调整堆(i,max):将i及之后(右、下)[……]

继续阅读