数据结构-堆
堆
什么是堆：堆是一棵完全二叉树
分类：
- 其根结点的值小于两个子结点的值，其余任何一个结点的值都小于其子结点的值——小根堆。
- 其根结点的值大于两个子结点的值，其余任何一个结点的值都大于其子结点的值——大根堆。
什么是完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
例子：一个完全二叉树
大根堆：
小根堆：
堆的存储结构：
一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。
例如上面的小根堆在数组的存储结构为：
| array | 5 | 24 | 33 | 25 | 46 | 42 | 57 | 28 | 48 | 60 | 48 | 99 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |