知识卡片

普通读书笔记卡 · 3613.a.2.b

最大堆增键应向上浮动

理解等级:中级

最大堆中把某节点的键增大后,可能只违反与父节点的关系;沿父链比较并交换,直到不再大于父节点,耗时 O(log n)。

MAX-HEAPIFY 是向下修复根过小的情形,方向相反,不能直接代替增键。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第6章 堆排序 · 查看原书依据

      As MAX-HEAP-INCREASE-KEY traverses this path, it repeatedly compares an element’s key to that of its parent, exchanging pointers and continuing if the element’s key is larger, and terminating if the element’s key is smaller, since the max-heap property now holds.

    参考来源

    - 位置:《算法导论(第4版)》第 6 章 6.5 节、Problems 与 Chapter notes(`OEBPS/chapter006.xhtml`,文本字符 [20000, 30000);图 6.5)。 - 结论依据:6.5 节 MAX-HEAP-INCREASE-KEY 提高 A[i] 后沿到根的路径反复比较父节点并交换;这是键变大后的向上修复。 - 原始内容:As M AX -H EAP -I NCREASE -K EY traverses this path, it repeatedly compares an element’s key to that of its parent, exchanging pointers and continuing if the element’s key is larger, and terminating if the element’s key is smaller, since the max-heap property now holds.