堆
堆是一种特殊的树形数据结构，它是一个完全二叉树，满足堆的性质。
- 最大堆 - 在最大堆中，一个节点的值必须是其在整个子树中的节点值中最大的。这个性质对于树中的所有节点都必须是递归成立的。
- 最小堆 - 在最小堆中，一个节点的值必须是其在整个子树中的节点值中最小的。这个性质对于树中的所有节点都必须是递归成立的。
在算法面试的背景下，堆和优先队列可以被视为相同的数据结构。当需要重复移除具有最高（或最低）优先级的对象，或者在插入与删除根节点之间需要穿插时，堆是一个很有用的数据结构。
学习资源
- 学习堆, basecs
- 使用堆排序堆化所有东西, basecs
- 堆, James Aspnes, Yale University
实现
| 语言 | API |
|---|---|
| C++ | std::priority_queue |
| Java | java.util.PriorityQueue |
| Python | heapq |
| JavaScript | N/A |
时间复杂度
| 操作 | 大O表示 |
|---|---|
| 查找最大/最小 | O(1) |
| 插入 | O(log(n)) |
| 删除 | O(log(n)) |
| 堆化（从给定的元素数组创建堆） | O(n) |
技巧
提及k
如果在问题中看到提到了顶部或底部的_k_，通常意味着可以使用堆来解决这个问题，例如在前K个高频元素中。
如果需要获取前_k_个元素，则使用大小为_k_的最小堆。遍历每个元素，将其推入堆中（对于Python的heapq，在推入之前翻转值以找到最大值）。每当堆的大小超过_k_时，删除最小元素，这将保证你拥有_k_个最大元素。
核心问题
这些是你练习这个主题时必须掌握的核心问题。
推荐练习问题
在你已经为这个主题进行了学习和练习核心问题之后，推荐你练习这些问题。
推荐课程
import AlgorithmCourses from '../_courses/AlgorithmCourses.md'