[数据结构] 堆与堆排序-摩杜云开发者社区

这篇文章使用 JavaScript 语言进行相关代码的编写。

数据结构——堆 heap

基本概念与性质

堆是一颗完全二叉树，根据父子节点之间值的大小关系可以分为：

大根堆：每一个节点的值 大于或等于 其子节点的值；
小根堆：每一个节点的值 小于或等于 其子节点的值；

堆数据结构的底层通常使用顺序表进行存储。

通过索引的计算可以快速得到子节点、父节点的值：

以 0 作为根节点的索引：（下文使用这种标准）

Parent(i) = (i-1)/2;
LeftChild(i) = i*2+1;
RightChild(i) = i*2+2;

以 1 作为根节点的索引：

Parent(i) = i/2;
LeftChild(i) = i*2;
RightChild(i) = i*2+1;

操作

一开始堆是一个空数组，最主要的两个API是插入和删除，这两个操作会在堆的头部和尾部进行操作，而这些操作会导致堆的性质丢失，因此每次进行插入和删除操作之后都需要重新维护堆的结构。

插入

插入操作将一个新的数据添加到堆的末尾，然后向上调整。

图片来源：二叉堆 - OI Wiki (oi-wiki.org)

删除

删除操作将根节点摘除，然后将堆的末尾的节点移动到堆的顶部，最后向下调整。

向上调整

对于某个节点（由一个明确的索引i指定），通过计算得到它的父节点的值，进行比较：

如果二者大小不满足堆性质，则交换（即上升），上升后继续与新的父节点进行比较；
如果二者大小满足堆性质，则终止。

时间复杂度与树的高度有关，这是完全二叉树，即O(log N)

function up(index){
  while(true){
    const parent = (index-1)>>1;
    if(this.arr[parent] < this.arr[index]){
      [this.arr[index], this.arr[parent]] = [this.arr[parent], this.arr[index]];
      index = parent;
    }else{
      break;
    }
  }
}

(index-1)>>1是通过位运算快速实现向下取整的除以2，有时候懒得写Math.floor...

向下调整

对于某个节点，通过索引计算得到左右两个子节点，分别进行比较：（以小根堆为例）

如果当前节点的值均小于左右两个子节点的值，则说明满足堆结构，终止；
如果左右两个子节点存在小于当前节点的值，那么找出最小值，最小的节点与当前节点进行交换（即下沉），下沉后继续与新的左右子节点进行比较。

时间复杂度：O(log N)

function down(index){
  while(true){
    let left = index*2+1;
    let right = index*2+2;
    let target = index;
    if(left<this.size() && this.arr[left]>this.arr[index]){
      target = left;
    }
    if(right<this.size() && this.arr[right]>this.arr[index]){
      target = right;
      if(left<this.size() && this.arr[left]>this.arr[right]){
        target = left;
      }
    }
    if(target!==index){
      [this.arr[index], this.arr[target]] = [this.arr[target], this.arr[index]];
      index = target;
    }else{
      break;
    }
  }
}

完整代码

class Heap {
  constructor(arr) {
    if(arr){
      this.arr = arr;
      for(let i=Math.floor((arr.length-1)/2); i>=0; i--){
        this._down(i);
      }
    }else{
      this.arr = [];
    }
  }

  size() {
    return this.arr.length;
  }

  push(val) {
    // 新的数据插入到尾部，然后向上调整
    this.arr.push(val);
    this._up(this.size() - 1);
  }

  top() {
    return this.arr[0];
  }

  pop() {
    // 没有数据了，返回null
    if (this.size() == 0) return null;
    // 只剩下一个数据了，直接弹出返回
    if(this.size() == 1)return this.arr.pop();
    // 先记录堆顶数据
    let top = this.top();
    // 将最后一个数据放到堆顶，然后向下调整
    let last = this.arr.pop();
    this.arr[0] = last;
    this._down(0);
    return top;
  }

  _up(index){
    while(true){
      const parent = (index-1)>>1;
      if(this.arr[parent] < this.arr[index]){
        [this.arr[index], this.arr[parent]] = [this.arr[parent], this.arr[index]];
        index = parent;
      }else{
        break;
      }
    }
  }

  _down(index){
    while(true){
      let left = index*2+1;
      let right = index*2+2;
      let target = index;
      if(left<this.size() && this.arr[left]>this.arr[index]){
        target = left;
      }
      if(right<this.size() && this.arr[right]>this.arr[index]){
        target = right;
        if(left<this.size() && this.arr[left]>this.arr[right]){
          target = left;
        }
      }
      if(target!==index){
        [this.arr[index], this.arr[target]] = [this.arr[target], this.arr[index]];
        index = target;
      }else{
        break;
      }
    }
  }
}

堆排序

堆排序是建立在堆这种数据结构上的选择排序。

首先建立大根堆，每次从根节点获取最大值，将最大值移动到堆的尾部，然后对剩下的前n-1个节点进行维护大根堆的操作。

即：每次选择最大值移动至尾部，再继续在剩下的数中继续查找最大值。

普通的选择排序是在线性表上寻找最大值，时间复杂度为 \(O(n)\) ，要查找 \(n\) 个最大值，因此时间复杂度为 \(O(n^2)\).
在大根堆上寻找最大值的时间复杂度是\(O(1)\)，而获取删除最大值之后的向下调整操作时间复杂度为\(O(\log n)\)，共寻找 \(n\) 个最大值，因此时间复杂度为 \(O(n\log n)\)。

考虑到排序算法的输入是一个乱序的数组，我们首要的任务是将一个普通的数组转换成一个大根堆。

方法：从 最后一个节点的父节点 ，逆序遍历数组，依次向下调整。

原理：自底向上，先保证子树满足堆性质，然后逐渐向上扩展直到整棵树都满足堆性质。

综上，堆排序总共分为两个步骤：

构造大根堆
选择排序 + 维护堆结构

代码

function heapSort(arr){
  const n = arr.length;
  // 从最后一个节点的父节点开始调整
  // 作用：构造大根堆
  for(let i=Math.floor(n/2)-1; i>=0; i--){
    heapify(arr, i, n);
  } 
  // 将大根堆的根节点和最后一个节点交换，同时维护堆的性质
  // 作用：排序
  for(let i=n-1; i>0; i--){
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, 0, i);
  }
}

// 调整堆
function heapify(arr, index, n){
  let left = 2*index+1;
  let right = 2*index+2;
  while(true){
    let largest = index;
    // 找到左右子树中的最大值
    if(left<n && arr[left]>arr[largest]){
      largest = left;
    }
    if(right<n && arr[right]>arr[largest]){
      largest = right;
    }
    // 如果最大值不是根节点，则交换
    if(largest!==index){
      [arr[index], arr[largest]] = [arr[largest], arr[index]];
      // 更新下一轮的索引
      index = largest;
      left = 2*index+1;
      right = 2*index+2;
    }else{
      break;
    }
  }
}

堆的其它应用

优先队列

优先队列是一种特殊的队列，每个元素都有一个优先级，按优先级顺序出队。刷算法题的时候经常会用到的辅助类PriorityQueue；

数组中的第 k 大（或小）元素

可以使用最小堆来高效找到第 \(k\) 大的元素。首先将前 \(k\) 个元素插入堆中，然后遍历数组的其余部分，更新堆，保持堆的大小为 \(k\)。最终堆顶元素就是第 \(k\) 大的元素。

合并多个有序链表

使用最小堆来维护每个有序列表的当前最小元素。每次从堆中取出最小元素，并将该元素所在列表的下一个元素插入堆中。重复该过程直到所有列表都被合并。

事件驱动模拟

在Node.js中，多个计时器回调就是使用最小堆记录的，每次事件循环进行到timer阶段，就检查堆顶计时器的剩余时间是否已到达：

如果未到达，则执行下一个阶段的回调任务；
如果已到达，则执行本阶段的所有已到达的定时器回调任务；
- 每个回调执行完成之后，如果是setInterval，则重新将任务添加到堆中。