[数据结构] 堆与堆排序
这篇文章使用 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是插入和删除，这两个操作会在堆的头部和尾部进行操作，而这些操作会导致堆的性质丢失，因此每次进行插入和删除操作之后都需要重新维护堆的结构。
插入
插入操作将一个新的数据添加到堆的末尾，然后向上调整。
删除
删除操作将根节点摘除，然后将堆的末尾的节点移动到堆的顶部，最后向下调整。
向上调整
对于某个节点（由一个明确的索引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，则重新将任务添加到堆中。
- 每个回调执行完成之后，如果是