Skip to content

为编码面试堆备忘单

原文:https://www.techinterviewhandbook.org/algorithms/heap/

简介

堆是专门的基于树的数据结构,它是满足堆属性的完整的树。

  • 最大堆——在最大堆中,一个节点的值必须是整个子树中最大的。对于树中的所有节点,相同的属性必须递归为真。
  • 最小堆——在最小堆中,一个节点的值必须是整个子树中所有节点值中最小的。对于树中的所有节点,相同的属性必须递归为真。

在算法访问的上下文中,堆和优先级队列可以被视为相同的数据结构。当需要重复移除具有最高(或最低)优先级的对象时,或者当插入需要穿插移除根节点时,堆是一种有用的数据结构。

学习资源

  • 学会爱堆,basecs
  • 用堆排序将所有的东西堆起来
  • 詹姆斯·阿斯彭斯,耶鲁大学

实现

语言 应用程序接口
C++ T2std::priority_queue
Java 语言(一种计算机语言,尤用于创建网站) T2java.util.PriorityQueue
计算机编程语言 T2heapq
Java Script 语言 不适用的

时间复杂度

操作 大 O
查找最大值/最小值 O(1)
插入 O(log(n))
去除 O(log(n))
Heapify(从给定的元素数组中创建一个堆) O(n)

技巧

提及k

如果你看到问题中提到了一个最高或最低的 k ,这通常是一个信号,表明可以使用堆来解决问题,比如在中的 Top K frequency Elements

如果你需要顶部的 k 个 T2 元素,使用一个最小堆,大小为 k 个 T4。遍历每个元素,将其推入堆中(对于 python heapq,在推入之前反转值以找到最大值)。每当堆大小超过 k 时,移除最小的元素,这将保证您拥有 k 个最大的元素。

基本问题

如果你在学习这个话题,这些是需要练习的基本问题。

推荐练习题

这些是在你为题目学习并练习了基本问题后推荐练习的问题。

推荐课程

AlgoMonsterT3】

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式,并有内容帮助你快速修改基本的数据结构和算法。最重要的是,AlgoMonster 不是基于订阅的——支付一次性费用,就可以获得终身访问今天加入七折优惠→

寻找编码面试:编码问题的模式

设计大师的这门课程扩展了推荐练习题中的问题,但从问题模式的角度来进行练习,这是一种我也同意的学习方法,我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题,并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式,而不是背答案! 现在获得终身使用权→

掌握编码面试:数据结构+算法

这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星,21.5k 评分,135k 学生),包含了价值 19 个小时的内容。像技术面试手册一样,它超越了编码面试,涵盖了简历,非技术面试,谈判。是一个全包!请注意,JavaScript 用于编码演示。 结账→



回到顶部