为编码面试堆备忘单

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

简介

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

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

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

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

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