搞定大厂算法面试之leetcode精讲12.堆
2023-03-20 15:00:45 时间
搞定大厂算法面试之leetcode精讲12.堆
视频讲解(高效学习):点击学习
目录:
延伸:
满二叉树:除叶子节点外,所有的节点都有两个子节点,这类二叉树称作满二叉树(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;
}
}
相关文章
- Windows 和 Linux 操作系统中存在的漏洞
- Windows 10系统电脑,无法开启网络发现怎么解决?解决网络故障方法
- Fedora 35 或将采用 WirePlumber 来管理 PipeWire
- 版本帝 Firefox 90 发布,移除内置的FTP支持
- Chrome 92稳定版发布下载:CPU占用下降、0.1秒完成钓鱼站点识别
- 两个 Docker 使用神技,99% 的人都不知道!
- HarmonyOS服务卡片-运动饮食健康卡片
- Windows 亲生的 Linux 子系统
- NVIDIA、Intel发布Windows 11驱动!Windows 11游戏特性曝光
- Windows 10必备5款高质量软件,每个都堪称神器
- 最新的Windows 11版本内置Teams程序,聊天不用其它软件了
- Windows 10自动更新老是弹出,怎么禁止更新,几种关闭系统更新方法
- Fedora 35 通过大量新提案,支持自适应扇区大小
- 微软开源内部 Linux 发行版 CBL-Mariner
- 烦人的Windows自动更新总是关不掉?一招帮您彻底解决
- 谷歌Chrome 92浏览器发布,网络钓鱼检测速度提高近50倍
- 如何优雅的在Linux下开机自动重启脚本
- 微软详解Windows 11右键菜单和共享菜单的改进
- UOS国产操作系统:致力于构建系统生态!2022有望替代Windows7
- Windows 11上:右键菜单功能、视觉风格大升级