8.4.2 堆的定义
原书定位
印刷页P358起,对应PDF第370页。下文为目视整理的知识提要;完整内容见原书对照。
堆可视为完全二叉树并按层序存入数组。大根堆父关键字不小于孩子,小根堆父不大于孩子;只约束祖先与后代,不约束兄弟大小,也不保证中序有序。
1 起始数组中,结点 的孩子为 ,非叶结点为 ;0 起始时孩子为 。升序原地堆排序用大根堆,把最大值逐次移到数组尾部。

大根堆与顺序数组,原书P358。
下级知识点
对应练习
关联知识
- 5.2.1.1 几种特殊的二叉树
- 6.4.2.1 Dijkstra 算法
- 6.4.2.2 Floyd 算法
- 7.3.2 平衡二叉树
- 8.4 选择排序
- 8.4.2.1 建堆与堆排序
- 8.4.2.2 堆的插入与删除
- 8.4.2.3 堆的应用与性能
原书对照
展开原书对照截图

