完全二叉树
堆就是一种具有特殊性质的完全二叉树。
完全二叉树是由满二叉树去掉最后一层右侧的若干节点而形成的二叉树结构。
完全二叉树有一个很优秀的性质，就是可以被存储在一片连续的数组空间中。
上面这个示意图，如果我们对它的每个节点进行编号，采用从上到下、从左到右的顺序依次标上 1 到 6。那么你仔细观察其中父节点编号与子节点编号之间的关系就会发现，如果父节点编号是 i，其左孩子的编号就是 2 * i，右孩子的编号就是 2 * i + 1。例如，我们以 3 号节点作为父节点，其左孩子的编号就是 2 * 3 = 6 号，如果有右孩子，那它右孩子的编号就一定是 2 * 3 + 1 = 7。
在一棵有 n 个节点的完全二叉树中，节点编号应该为 1 到 n。这样，我们就可以使用数组的 1 到 n 位对应于这 n 个节点。由于完全二叉树父节点与子节点编号之间的特殊计算关系，因此只要我们知道父节点编号，就可以通过计算得到子节点编号。
即使我们将完全二叉树的所有数据，存储在一个连续的数组空间中，也不会破坏其特殊的树形结构信息。也就是说，一棵完全二叉树可以对应到一段连续的数组空间，而根据数组空间的内容，我们也可以唯一地还原成一棵完全二叉树。
实际上，在计算机中，我们会把数组作为完全二叉树的实际存储结构，而完全二叉树，则是我们重新看待这段数组信息的思维逻辑结构。
堆结构的定义
堆可以分为两类，小顶堆和大顶堆。
- 小顶堆:如果在一棵完全二叉树中，每个父节点的值都要小于其两个子节点的值，我们就管这种结构叫做小顶堆。
- 大顶堆:大顶堆就是每个父节点的值要大于其两个子节点的值。
根据小顶堆的性质定义，我们可以轻松得知，小顶堆中的最小值一定放在了根节点，也就是存储在数组中的第一个位置。如果我们将数组中的所有元素看成一个集合的话，那小顶堆的作用就非常明显了，就是维护这个集合中的最小值。
堆的实际存储结构是数组，这个数组是一段从下标 1 开始的连续存储空间。
堆的插入操作
假设我们想要在堆中放入一个新的元素 1，那么我们可以将这个新的元素，放置到整个数组的最后一位。对应到完全二叉树的思维逻辑结构中，就是向树中的最后一层添加了一个新的叶节点。
这一步的操作叫做元素放置。你会看到这么做之后，数组的结构就不满足小顶堆的性质了。所以下一步，我们要调整数组的结构，让它依然满足堆的性质。
由于堆的性质定义中，只规定了父节点与子节点之间的大小关系，所以，我们的调整操作只需要维护父子节点之间的大小关系即可。也就是说，新插入的元素 1，只需要和其父节点进行比较。
结合上面的示意图，我来说一下具体的操作。由于 1 比 4 小，所以我们把 1 交换到 4 的位置，然后让 1 再继续向上跟当前的父节点比较。因为 1 比 2 小，所以再让它们交换。这一步叫做向上调整，它的原理就是在当前元素值小于其父节点值的时候，交换子节点与父节点值的位置，就这样一直向上调整，直到当前节点大于父节点的值或者调整到了堆顶。
这样一来，经过元素放置 以及 2 次 向上调整 以后，堆中就增加了一个新元素，还依然满足堆的性质定义。这样，我们就完成了向堆中插入元素的操作。具体过程如图所示：
堆的删除最值操作
堆的删除操作是有局限性的，这怎么理解呢？我们可以从删除操作的定义入手。堆的删除操作也叫做删除最值元素，对小顶堆进行删除操作就是删除最小的元素，其实就是删除数组中第一位的元素。
那为了保证删除最值元素以后，整个堆结构的存储还是从数组的第 1 位开始的，所以我们第一步要做的就是元素覆盖，也就是用堆的最后一位元素，覆盖掉堆顶元素。
接下来，我们就需要通过适当调整，让它重新满足堆的性质。调整的方法其实也很简单，就是从堆顶位置开始，每次从当前元素所在三元组中找到一个最小值，与当前元素交换。交换后，让当前位置的元素继续和下面两个元素比较，如果这个三元组中依然有最小值，那我们就继续向下调整，直到当前元素是三元组中的最小值为止。
于是，针对这个小顶堆，我们通过 1 次 元素覆盖 和 1 次 向下调整，就完成了删除最值元素的操作。
优先队列
堆其实就是一个数组，在插入元素时，从数组的末尾放入元素，而删除元素时，是从数组的头部移出元素。
队列结构就是从尾部入元素，从头部出元素。而且堆这种结构，每次从头部移出的都是当前堆中的最值元素。所以，如果我们把堆的存储结构看成是一个队列的话，那堆就是一种可以灵活控制元素出队优先级的数据结构，我们管这种结构就叫做优先队列。
总结
- 堆是一种特殊的完全二叉树，它可以分为两类，分别是大顶堆和小顶堆。在小顶堆中，每个父节点的值都要小于其两个子节点的值，大顶堆则相反。
- 堆有两种基本的结构操作，插入操作和删除最值操作。在插入操作中，我们是将新元素放到整个堆结构的末尾，然后对新插入的元素执行向上调整的操作，一直调整到满足堆的结构性质为止。而在删除操作中，我们是将堆顶元素弹出以后，再将堆的尾部元素移动到堆顶，对其执行向下调整的操作，一直调整到满足堆的结构性质为止。
- 堆是实现优先队列的其中一种方式，优先队列每次出队的元素，都是队列中优先级最大的值。
- 堆是用来维护集合最值的高效数据结构。
