使用数组构建堆结构的过程和堆排序原理

Posted by Mars 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. 堆排序

完成了堆的建立,堆顶的元素就是堆中最大(或最小)元素。堆排序过程如下:

  1. 交换堆顶元素(数组元素arr[0])和堆最后一个元素(数组元素arr[arr.length-1]);
  2. 当前最后一个元素排序完成,堆的尺寸-1(也就是数组右边界-1)。然后对此时刚交换完成的堆顶新元素,进行堆化处理,将其放置在当前堆中正确的位置,保证当前堆的结构;
  3. 重复执行1步骤,直到堆尺寸为1(只剩顶部一个元素),排序完成。

注意:

对于大顶堆,排序后的结果为升序;

对于小顶堆,排序后的结果为降序。

Keywords: Data Structure
previousPost nextPost
已经有 1000000 个小伙伴看完了这篇推文。