算法014_堆和堆的向下调整

什么是堆

• 堆：一种特殊的完全二叉树结构
  • 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大
  • 小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小

大根堆

大根堆

小根堆

小根堆

类比权利结构，比如 国家主席 --> 总理 --> 省长 --> 市长 --> 县长 --> 村民

堆的向下调整性质
（1）假设根节点的左右子树都是堆，但根节点不满足堆的性质
（2）可以通过一次向下的调整来将其变成一个堆

节点的左右子树都是堆，但自身不是堆
2 比 9 和 7 都小，不是堆，但是它下面都满足堆的特性

把 2 拿掉，然后把 9 放到原先 2 的位置

如果把 2 放到空出，它依然比 8 和 5 小，因此 2 不能放在空出，得把 8 移到空白处

2 比 6 和 4 都小，因此 2 不能放在空白处，把 6 提上来

再把 2 放到空白处，此时就满足了大根堆的特性

当根节点的左右子树都是堆的时候，可以通过一次向下的调整来将其变换成一个堆