数据结构：堆（Heap）
堆的概念
堆（Heap）是数据结构中一种特殊的计算机结构，是一种特殊的完全二叉树，为非线性的数据结构，一般用于优先队列、堆排序、Top-k 的问题等等。
完全二叉树是二叉树中的一种，它的节点满足以下规律，有且只有以下三种情况：
- 有左右两个孩子
- 只有左孩子
- 没有孩子（叶子节点）
叶子节点只可能在最大的两层出现且在最左层的叶子节点都集中在左侧。如下图理解：
注意：除了最后一层，如果每个父节点的孩子节点都有两个，它属于满二叉树，注意区别！
堆的性质
结构特性
从上面我们可以观察到，除了一层外，其它层是满层的，最后一层居左对齐。
堆序性质
可以看到，它的节点关键字是有序的，因此我们又可以将堆分为两类：
可以观察到大顶堆中，它的根节点关键字是整个树中是最大的，而每个父节点的孩子节点都要小于它的父节点。在小顶堆中，整个树的根节点关键字最小，且每个父节点关键字小于孩子节点的关键字。除此之外，有一个要补充的点：除了根节点的关键字处于两个极端之外，父节点的关键字是可以等于它的孩子节点的。
**大顶堆：**父节点的值 >= 子节点的值（根节点在整个树中最大）
**小顶堆：**父节点的值 <= 子节点的值（根节点在整个树中最小）
堆的物理逻辑 & 思维逻辑
咱们知道，堆是一种完全二叉树，但是我们选择的是数组方式的存储，没有用链表。我们的堆元素是依次存储到数组里面的，比如根节点对应数组下标 0（或 1），根节点的左子节点对应数组的 1（或 2），根节点的右子节点对应数组的 2（或 3），依次类推满足：从上到下，从左到右。思维逻辑方便我们在查找问题，以及写各种操作时借助二叉树来直观的体现，如果我们在数组上操作进行思维操作，那么会很乱。
堆的节点对应关系
因为我们是数组实现，节点下标之间的索引存在固定的数学关系：
如果堆在数组中的下标是从 0 开始，那么满足： 假如父节点在数组的下标为 i，它的左孩子节点在数组的下标为 2 * i + 1，右节点数组下标为：2 * i + 2
如果堆在数组中的下标是从 1 开始，那么满足： 假如父节点在数组的下标为 i，它的左孩子节点在数组的下标为 2 * i，右节点数组下标为：2 * i + 1
假如子节点在数组的下标为 k，它的父节点在数组中的下标为 (k - 1) / 2
例如：
