大厂算法面试之 leetcode 精讲 12. 堆
视频解说（高效学习）: 点击学习
目录：
1. 开篇介绍
2. 工夫空间复杂度
3. 动静布局
4. 贪婪
5. 二分查找
6. 深度优先 & 广度优先
7. 双指针
8. 滑动窗口
9. 位运算
10. 递归 & 分治
11 剪枝 & 回溯
12. 堆
13. 枯燥栈
14. 排序算法
15. 链表
16.set&map
17. 栈
18. 队列
19. 数组
20. 字符串
21. 树
22. 字典树
23. 并查集
24. 其余类型题
延长：
满二叉树 ：除叶子节点外，所有的节点都有两个子节点，这类二叉树称作满二叉树（Full Binarry Tree)，如下图：
齐全二叉树 ：若设二叉树的高度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左间断缺若干结点，这就是齐全二叉树。
堆是一个齐全二叉树，所以咱们能够采纳数组实现，不会节约太多空间，堆中的每个节点的值总是不大于或不小于其父节点的值，堆分为大顶堆和小顶堆，大顶堆堆顶是元素中最大的一个，小顶堆堆顶是最小的，在向堆中退出元素的时候，能动静调整堆内元素的程序，始终保持堆的性质。
堆的特点：
- 外部数据是有序的
- 能够弹出堆顶的元素，大顶堆就是弹出最大值，小顶堆就是弹出最小值
- 每次退出新元素或者弹出堆顶元素后，调整堆使之从新有序仅须要 O(logn) 的工夫
堆的实现
- 用数组实现，堆从上到下，从左到右一一对应数组中的元素
- 节点父节点索引
parentIndex = [(index - 1) / 2]，左节点索引leftIndex = index * 2 + 1，右节点索引rightIndex = index * 2 + 2 - 第一个非叶子节点是
[size / 2]
向堆中增加元素
- 把新数据增加到树的最初一个元素，也就是数组的开端
- 把开端节点向上调整，即 bubbleUp
- 工夫复杂度
O(logn)
动画过大，点击查看
弹出堆中的元素
- 替换根节点与最初一个节点的值
- 删除最初一个节点
- 把根节点向下调整
- 工夫复杂度
O(logn)
动画过大，点击查看
从一个数组中取出最小值的复杂度：
残缺代码
class Heap {constructor(comparator = (a, b) => a - b, data = []) {
this.data = data;
this.comparator = comparator;// 比拟器
this.heapify();// 堆化}
heapify() {if (this.size() < 2) return;
for (let i = Math.floor(this.size()/2)-1; i >= 0; i--) {this.bubbleDown(i);//bubbleDown 操作
}
}
peek() {if (this.size() === 0) return null;
return this.data[0];// 查看堆顶
}
offer(value) {this.data.push(value);// 退出数组
this.bubbleUp(this.size() - 1);// 调整退出的元素在小顶堆中的地位
}
poll() {if (this.size() === 0) {return null;}
const result = this.data[0];
const last = this.data.pop();
if (this.size() !== 0) {this.data[0] = last;// 替换第一个元素和最初一个元素
this.bubbleDown(0);//bubbleDown 操作
}
return result;
}
bubbleUp(index) {while (index > 0) {const parentIndex = (index - 1) >> 1;// 父节点的地位
// 如果以后元素比父节点的元素小，就替换以后节点和父节点的地位
if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {this.swap(index, parentIndex);// 替换本人和父节点的地位
index = parentIndex;// 一直向上取父节点进行比拟
} else {break;// 如果以后元素比父节点的元素大，不须要解决}
}
}
bubbleDown(index) {const lastIndex = this.size() - 1;// 最初一个节点的地位
while (true) {
const leftIndex = index * 2 + 1;// 左节点的地位
const rightIndex = index * 2 + 2;// 右节点的地位
let findIndex = index;//bubbleDown 节点的地位
// 找出左右节点中 value 小的节点
if (
leftIndex <= lastIndex &&
this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
) {findIndex = leftIndex;}
if (
rightIndex <= lastIndex &&
this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
) {findIndex = rightIndex;}
if (index !== findIndex) {this.swap(index, findIndex);// 替换以后元素和左右节点中 value 小的
index = findIndex;
} else {break;}
}
}
swap(index1, index2) {// 替换堆中两个元素的地位
[this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
}
size() {return this.data.length;}
}