Algorithms study cheatsheets
Coding interview 的 Heap cheatsheet
Heap 学习指南，包含练习题、技巧、时间复杂度与推荐资源
Introduction
Heap 是一种特殊的树结构（complete tree），并满足 heap property。
- Max heap - 节点值必须是其子树中的最大值，这一性质递归成立。
- Min heap - 节点值必须是其子树中的最小值，这一性质递归成立。
在算法面试里，heap 和 priority queue 基本可视为同一种结构。Heap 适用于需要反复删除最高（或最低）优先级元素，或需要插入与删除 root 交替进行的场景。
Learning resources
- Learning to Love Heaps, basecs
- Heapify All The Things With Heap Sort, basecs
- Heaps, James Aspnes, Yale University
Implementations
| Language | API |
|---|---|
| C++ | std::priority_queue |
| Java | java.util.PriorityQueue |
| Python | heapq |
| JavaScript | N/A |
Time complexity
| Operation | Big-O |
|---|---|
| Find max/min | O(1) |
| Insert | O(log(n)) |
| Remove | O(log(n)) |
| Heapify (create a heap out of given array of elements) | O(n) |
Techniques
Mention of k
如果题目提到 top 或 lowest k，通常就是 heap 的信号，例如 Top K Frequent Elements。
如果需要 top k，用 size 为 k 的 Min Heap。遍历元素并 push 进 heap（对 python heapq 来说，如果要找 max，需要先取负）。当 heap size 超过 k 时，pop 最小值即可保证剩下的是 k 个最大元素。
Essential questions
这些是该 topic 必练题。
Recommended practice questions
这些是在掌握基础后推荐练习的题目。