堆¶
堆(Heap）是一个完全二叉树。
跟节点比所有子节点大(或者小)
对于任意子树，其根节点也必须比它的子节点大(或者小)。
如果所有父节点都比子节点大，就是大根堆,反之就是小跟堆
数组实现堆¶
堆在逻辑结构上是一颗树，但物理结构上可以用数组实现。
对于索引为i的节点
| 节点 | 索引 |
|---|---|
| 节点 | i |
| 左孩子索引 | 2i+1 |
| 右孩子索引 | 2i+2 |
| 父节点 | (i-1)/2 |
插入过程¶
将新元素放到数组尾部
新元素从所在位置开始往上调整
删除堆顶过程¶
先将堆顶元素删掉
将最后一个元素放到堆顶位置
从堆顶往下调整，使得堆仍然是一个大根堆或小根堆
删除堆中任意位置元素¶
- 将最后一个元素位置放到要删除的位置，此时需要比较这两个元素的大小，并适当调整堆
- 在大堆情况下，如果最后一位的元素比要删除的值大，那么就要往上调整堆；如果最后一位的元素比要删除的值小，那么就要往下调整堆
- 小堆情况下，跟大堆调整相反
调整¶
从当前位置，依次往上与父节点比较替换
或者依次往下与子节点比较替换