知识卡片

普通读书笔记卡 · 3613.b

堆排序维护已排序后缀

理解等级:中级

堆排序先在线性时间建最大堆,然后反复将堆根最大值与当前堆尾交换,缩小 heap-size 并重新堆化根。堆前缀始终保留未排序元素,后缀按序积累较大元素;额外空间 O(1),总时间 O(n log n)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The HEAPSORT procedure takes O(n lg n) time, since the call to BUILD-MAX-HEAP takes O(n) time and each of the n – 1 calls to MAX-HEAPIFY takes O(lg n) time.

    参考来源

    - 位置:《算法导论(第4版)》第 6 章(`OEBPS/chapter006.xhtml`,文本字符 [15000, 20000);图 6.1–6.4 与公式图 Art_P298–P304)。 - 结论依据:6.4 节 HEAPSORT 每轮将根与堆尾交换,heap-size 减一后堆化根;图 6.4 的后缀为按序积累的最大键,6.3 节建堆为 O(n)。 - 原始内容:The H EAPSORT procedure takes O ( n lg n ) time, since the call to B UILD -M AX -H EAP takes O ( n ) time and each of the n – 1 calls to M AX -H EAPIFY takes O (lg n ) time.