知识卡片

普通读书笔记卡 · 5654.d.1.e.2.a.4

固定小顶堆保留最大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 个元素 示例代码如下: