知识卡片

普通读书笔记卡 · 3613.d.11 · 生成模型:未记录

批量建堆从下向上做下沉

理解等级:中级

已有全部n项数组时,可从最后一个内部节点⌊n/2⌋−1开始,依次到根,对每棵子树做向下调整。孩子子树先已成堆,父节点下沉后才保证更大子树也是堆;叶子无需调整。

这是按节点从下往上处理、每次把失序父项向下沉,不是原文误写的像heap_insert一样逐项上浮。大多数节点高度很小,按高度分组总工作可界为O(n·Σ h/2ʰ)=O(n);不能把每个节点都按最大log n高度收费。

逐项插入则可能每次都上浮较深,比较/交换最坏O(n log n)。批量线性建堆不把后续全部排序也变线性,更不包含本书逐项realloc的潜在复制成本。MIT二叉堆讲义,第6页(2026-11-06读取并核对下沉方向/线性结论)。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      构建一个堆,要使用本章提到的接口heap_insert,每次插入一个元素时就调用一次此接口。由于heap_insert的时间复杂度为O(lg n),因此构建一个堆所需要的运行时间为O(nlg n)。是否有其他可代替的方法来构建一个堆,使复杂度降为O(n)? 答:为了避免重复地调用函数heap_ins

    参考来源

    - 位置:《算法精解:C语言描述》第10章《问与答》(spine1319;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1286.html;u183-ch10-012)。 - 结论依据:183首问全部问答实读并读取MIT原始课程线性建堆相关页,纠正上浮方向、半数调整解释和成本适用范围。 - 原始内容:构建一个堆,要使用本章提到的接口heap_insert,每次插入一个元素时就调用一次此接口。由于heap_insert的时间复杂度为O(lg n),因此构建一个堆所需要的运行时间为O(nlg n)。是否有其他可代替的方法来构建一个堆,使复杂度降为O(n)? 答:为了避免重复地调用函数heap_ins