使用数组构建堆结构的过程和堆排序原理
Posted by Mars . Modified at
使用数组构建堆结构的过程和原理:
heapify()函数的含义和代码,构建起始位置和过程等。
1. 堆结构的特点
一个完全二叉树,如果每一个父节点值都大于等于(或小于等于)它子节点的值,则这个二叉树称为一个堆。
- 大顶堆:任一父节点值大于子节点值(最大值在根节点)
- 小顶堆:任一父节点值小于子节点值(最小值在根节点)
2. 数组构建堆结构过程
对于一个任一数组arr,可以使用下面的方法将其转化为一个堆。
从任一叶子节点向前遍历,对每一个节点使用heapify(arr,index)方法,直到index === 0(根节点)为止。
2.1 heapify()函数的作用
heapify(arr,index)函数的作用是:
将arr中index位置的元素,放在它子树中正确的位置。
因此,从叶子节点开始,向上遍历执行heapify()直到根节点,可以保证整棵树的元素都按堆的原则,放在了正确的位置上。(堆构建完成)
// heapify函数的实现:i从0开始
// rightEdge是堆排序的右边界,为了之后的堆排序使用。从原数组右侧去掉若干元素,剩下的数组部分仍然是一个堆。
function heapify(arr, i, rightEdge){
let left = 2 * i + 1, right = 2 * i + 2
let largest = i
if (left <= rightEdge && arr[left] > arr[largest]) largest = left
if (right <= rightEdge && arr[right] > arr[largest]) largest = right
if (largest !== i){
[arr[largest],arr[i]] = [arr[i],arr[largest]]
heapify(arr, largest, rightEdge)
}
}
2.2 数组构建堆的起始位置,可以不是最后一个节点
可以使用Math.floor(arr.length/2)
或Math.floor(arr.length/2)-1
来作为第一个节点。
证明如下图:
Math.floor(arr.length/2)-1返回的总是最后一个叶子节点的父节点。
3. 堆排序
完成了堆的建立,堆顶的元素就是堆中最大(或最小)元素。堆排序过程如下:
- 交换堆顶元素(数组元素
arr[0]
)和堆最后一个元素(数组元素arr[arr.length-1]
); - 当前最后一个元素排序完成,堆的尺寸-1(也就是数组右边界-1)。然后对此时刚交换完成的堆顶新元素,进行堆化处理,将其放置在当前堆中正确的位置,保证当前堆的结构;
- 重复执行1步骤,直到堆尺寸为1(只剩顶部一个元素),排序完成。
注意:
对于大顶堆,排序后的结果为升序;
对于小顶堆,排序后的结果为降序。
堆的使用技巧
- 动态选取集合元素的最小值:建立小顶堆,每次取堆顶元素;
- 动态选取集合元素的最大值:建立大顶堆,每次取堆顶元素;
- 动态选取集合元素中的
n
个最大值:建立小顶堆,当堆中的元素个数=== n
时,再加入的元素与堆顶元素(当前最小元素)进行比较,如果大于其值,则将堆顶元素弹出,将当前元素加入堆,同时更新选取的结果; - 动态选取集合元素中的
n
个最小值:建立大顶堆,当堆中的元素个数=== n
时,再加入的元素与堆顶元素(当前最大元素)进行比较,如果小于其值,则将堆顶元素弹出,将当前元素加入堆,同时更新选取的结果; - 动态选取集合元素中第
k
大的值:- 建立对顶堆。上面为小顶堆,下面为大顶堆;
- 上面小顶堆的最大体积为
k
; - 加入元素时,如果上面小顶堆的体积
< k
,则直接加入上面的小顶堆; - 如果体积
=== k
,则新加入的元素e
与小顶堆堆顶元素进行比较:- 如果新元素更大,则弹出小顶堆堆顶元素,将其加入下方大顶堆,同时将当前元素
e
加入上方小顶堆; - 否则, 直接将当前元素
e
加入下方大顶堆。
- 如果新元素更大,则弹出小顶堆堆顶元素,将其加入下方大顶堆,同时将当前元素
- 当小顶堆体积
=== k
时,当前第k
大的元素就是小顶堆的堆顶元素。