堆

二叉堆

二叉堆是一种完全二叉树，每个节点存有一个权值。

完全二叉树的定义：

1. 完全二叉树只允许最后一行不为满

2. 且最后一行必须从左往右排序

3. 最后一行元素之间不可以有间隔

注意：二叉堆不是二叉搜索树，并不满足左节点小于右节点

堆序性：

• 大根堆：堆的父节点权值大于子节点
• 小根堆：堆的父节点权值小于子节点

由堆序性可知，堆的节点处存有最大值或最小值。

实现形式：

堆因为具有堆序性，可以使用数组/链表来实现。数组存储堆的顺序为层序遍历。

因为堆是完全二叉树，所以每个下标和树的每个位置是一一对应的。

假设父节点的索引是 $i$，则其左节点的索引是 $2i+1$，右节点的索引是 $2i+2$。

基本操作

上浮

以大根堆为例

将叶子节点根据堆序性向上调整，若叶子节点小于父节点，对于大根堆而言不满足堆序性，此时考虑交换叶子节点与父节点，如此循环，即可恢复堆序性。

下沉

以大根堆为例

将父节点根据堆序性向下调整，若父节点小于叶子节点，对于大根堆而言不满足堆序性，此时考虑交换父节点和较大的叶子节点，如此循环，即可恢复堆序性。