堆

---

堆(Heap）是一个完全二叉树。
跟节点比所有子节点大(或者小)
对于任意子树，其根节点也必须比它的子节点大(或者小)。
如果所有父节点都比子节点大，就是大根堆,反之就是小跟堆

数组实现堆

堆在逻辑结构上是一颗树，但物理结构上可以用数组实现。

对于索引为i的节点

节点	索引
节点	i
左孩子索引	2i+1
右孩子索引	2i+2
父节点	(i-1)/2

插入过程

将新元素放到数组尾部
新元素从所在位置开始往上调整

删除堆顶过程

先将堆顶元素删掉
将最后一个元素放到堆顶位置
从堆顶往下调整，使得堆仍然是一个大根堆或小根堆

删除堆中任意位置元素

• 将最后一个元素位置放到要删除的位置，此时需要比较这两个元素的大小，并适当调整堆
• 在大堆情况下，如果最后一位的元素比要删除的值大，那么就要往上调整堆；如果最后一位的元素比要删除的值小，那么就要往下调整堆
• 小堆情况下，跟大堆调整相反

调整

从当前位置，依次往上与父节点比较替换
或者依次往下与子节点比较替换