知识卡片
固定小顶堆保留最大K项
先把前k项放入小顶堆,堆顶就是当前保留集合中最小的一项。新元素若大于堆顶,便替换它;否则不能改善已有最大k项集合,可直接忽略。
遍历中始终维持已见元素的最大k项,适用于数据流,时间O(nlogk)、辅助O(k),初始化方法会影响小项成本。需0≤n;堆内并未整体排序,重复值按元素计,不能当作k个不同键。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
若当前元素大于堆顶元素,则将堆顶元素出堆,并将当前元素入堆。 4. 遍历完成后,堆中保存的就是最大的 个元素。 。 第8 章 堆 hello‑algo.com 186 图8‑8 基于堆寻找最大的k 个元素 示例代码如下:
参考来源
- 位置:《Hello 算法--Go版本》第08章《堆》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[22724,22834))
- 结论依据:实际TopK四步/小堆图和topKHeap代码支持不变量与输入边界。
- 原始内容:若当前元素大于堆顶元素,则将堆顶元素出堆,并将当前元素入堆。 4. 遍历完成后,堆中保存的就是最大的 个元素。 。 第8 章 堆 hello‑algo.com 186 图8‑8 基于堆寻找最大的k 个元素 示例代码如下: