知识卡片

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

堆用局部次序维护极值

理解等级:中级

二叉堆保持完全树形状,并使大顶堆每个父值不小于孩子,小顶堆则不大于孩子。因此根一定是全局极值,其他位置却不保证整体有序。

优先队列是按优先级取出的抽象,堆是常见实现;两者并非定义上完全等同。完全形状适合紧凑数组表示,和搜索树左右范围有序的条件不同。数据结构堆与内存分配区“堆”也只是同名。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      「堆heap」是一种满足特定条件的完全二叉树,主要可分为两种类型,如图8‑1 所示。 ‧「小顶堆min heap」:任意节点的值 其子节点的值。 ‧「大顶堆max heap」:任意节点的值 其子节点的值。 图8‑1 小顶

    参考来源

    - 位置:《Hello 算法--Go版本》第08章《堆》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[15594,15704)) - 结论依据:实际两类堆/完全形状/优先队列抽象,关系清晰不把heap当有序数组。 - 原始内容:「堆heap」是一种满足特定条件的完全二叉树,主要可分为两种类型,如图8‑1 所示。 ‧「小顶堆min heap」:任意节点的值 其子节点的值。 ‧「大顶堆max heap」:任意节点的值 其子节点的值。 图8‑1 小顶