搞定大厂算法面试之leetcode精讲12.堆
2021/11/30 12:36:23
本文主要是介绍搞定大厂算法面试之leetcode精讲12.堆,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
大厂算法面试之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; } }
这篇关于搞定大厂算法面试之leetcode精讲12.堆的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain