8.4.2.2 堆的插入与删除

教材导航 · 第8章

原书定位

印刷页P360起,对应PDF第372页。下文为目视整理的知识提要;完整内容见原书对照。

插入放数组末端,再沿父指针上滤;删除堆顶由末尾记录补根,再向下调整。单次最坏 O(log⁡n)O(\log n),查看堆顶 O(1)O(1)。

顺序堆应把实际容量与当前元素个数分开,满时如何扩容由应用决定;题设固定空间时不能无限插入。堆可实现优先队列,出队按优先级而非先进先出。

堆尾插入与上滤

堆尾插入与上滤,原书P360。

对应练习

8.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P360,PDF第372页