8.4.2 堆的定义

教材导航 · 第8章

原书定位

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

堆可视为完全二叉树并按层序存入数组。大根堆父关键字不小于孩子,小根堆父不大于孩子;只约束祖先与后代,不约束兄弟大小,也不保证中序有序。

1 起始数组中,结点 ii 的孩子为 2i,2i+12i,2i+1,非叶结点为 1…⌊n/2⌋1\ldots\lfloor n/2\rfloor;0 起始时孩子为 2i+1,2i+22i+1,2i+2。升序原地堆排序用大根堆,把最大值逐次移到数组尾部。

大根堆与顺序数组

大根堆与顺序数组,原书P358。

下级知识点

对应练习

8.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P358,PDF第370页

原书对照,原书P359,PDF第371页