【算法基础】堆⭐⭐⭐

一、堆

1. 堆的概念

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
（1）堆中某个结点的值总是不大于或不小于其父结点的值；
（2）堆总是一棵完全二叉树。
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是非线性数据结构，相当于一维数组，有两个直接后继。

2. 堆的基本操作与实现原理

如上图所示👆，堆就是二叉树结构，以小根堆为例，每个节点都有两个子节点（除了最后两层），而且该节点比两个子节点都要小。我们需要准备两个函数：down(); 和 up()，down表示当前元素太大了，需要向下移动，此时需要在当前节点、两个子节点，这三个节点中选择最小的点与当前节点交换，逐渐下沉，直到无法交换为止；up表示当前元素太小了，需要上移，但是此时只需要比较当前节点和父节点的大小关系，若比父节点小，则交换，递归，直到无法交换（因为这三个节点的最小值一定是当前节点和父节点之间选择，另一个子节点一定 >= 父节点）。

堆通常使用一维数组来存储，父节