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

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

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

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

注意:

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

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

堆的使用技巧

  1. 动态选取集合元素的最小值:建立小顶堆,每次取堆顶元素;
  2. 动态选取集合元素的最大值:建立大顶堆,每次取堆顶元素;
  3. 动态选取集合元素中的n个最大值:建立小顶堆,当堆中的元素个数=== n时,再加入的元素与堆顶元素(当前最小元素)进行比较,如果大于其值,则将堆顶元素弹出,将当前元素加入堆,同时更新选取的结果;
  4. 动态选取集合元素中的n个最小值:建立大顶堆,当堆中的元素个数=== n时,再加入的元素与堆顶元素(当前最大元素)进行比较,如果小于其值,则将堆顶元素弹出,将当前元素加入堆,同时更新选取的结果;
  5. 动态选取集合元素中第k大的值:
    1. 建立对顶堆。上面为小顶堆,下面为大顶堆;
    2. 上面小顶堆的最大体积为k
    3. 加入元素时,如果上面小顶堆的体积< k,则直接加入上面的小顶堆;
    4. 如果体积=== k,则新加入的元素e与小顶堆堆顶元素进行比较:
      1. 如果新元素更大,则弹出小顶堆堆顶元素,将其加入下方大顶堆,同时将当前元素e加入上方小顶堆;
      2. 否则, 直接将当前元素e加入下方大顶堆。
    5. 当小顶堆体积=== k时,当前第k大的元素就是小顶堆的堆顶元素。

对顶堆

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