二叉堆分为两种，最大堆和最小堆，我们只讨论最小堆的性质，最大堆具有相同的原理。
最小堆是一种符合下面两个特性的树形结构：
- 最小堆是一颗完全二叉树，即最小堆的每个节点要么没有子节点，要么只有一个左子节点，要么有两个子节点。
- 最小堆的每个节点都小于等于它的子节点。
堆的基本操作
从性质2可以得出一个结论，最小堆的堆顶元素，一定是堆中最小的元素。
最小堆可以支持以下几种基本操作：
- pop，移除堆顶元素，然后堆要做一些操作，维护堆的性质，这样保证了每次都能pop出堆中最小元素
- peek，查看堆顶元素
- push，向堆中添加元素，这个元素要被移动到合适的位置，以维护堆的性质
- union，将两个堆合并成一个堆，需要额外的操作维护堆的性质
这其中，peek的时间复杂度是O(1)的，pop和push的操作是O(logN)的，union操作是O(N+M) 的，其中N和M是堆元素个数。这里先有个概念即可，下面会详细分析这些操作。
由堆的这些性质可以看出来，堆在处理动态数据的时候有非常大的优势，在很多优先级相关的场景下发挥着重大的作用。
堆删除和新增元素后的维护操作，我们分别称之为shiftUp和shiftDown，下图展示了一个最小堆的添加和删除过程。
从上图可以直观的看出，删除堆顶元素后的shiftDown操作和添加元素后的shiftUp的时间上限和堆的高度有关系，二叉树的高度是logN的，所以我们说堆的pop和push的操作时间复杂度是O(logN)的。
堆的存储
谈到树结构，大家可能首先想到的是使用链表的方式存储，确实使用引用关联节点的方式用起来非常灵活。但是对于完全二叉树来说，使用数组存储是一种更加优雅的实现方法。同样使用数组实现二叉堆是一种非常经典的实现，下面我们就来谈谈如何使用数组实现二叉堆的。
先看一幅图
从图中淡蓝色的索引不难发现，数组中元素是按照二叉树的广度优先遍历顺序存储的，由于堆是完全二叉树，所以存储数组中元素一定是连续的。
存的问题解决了，那怎么读取呢，堆的基本操作需要频繁的获取当前节点的父节点或者子节点的。基于链表的实现方式非常简单的就能引用获取，那么基于数组的实现又如何获取呢？
我们还是重点关注上图中淡蓝色字体标注的树节点下标，不难发现：
- 每个节点的左子节点下标 = 自身下标 * 2 ，右子节点下标 = 自身下标 * 2 + 1
- 每个节点父节点下标 = 自身下标 / 2，这里的除是向下取整的。
如果你对这个结果持怀疑态度，可以使用数学归纳法证明一下，也比较简单，这里就不在赘述了
可能你注意到了，数组的起始下标是从1开始的，这也是一种比较经典的实现方式（可以减少计算次数），数组的起始下标从0开始，也有相似的性质。
解决了存取问题，我们不妨看一下核心代码的实现
堆的实现
我用Java代码实现了一个二叉堆，详细的代码可以在我的GitHub上可以看到，下面是一些核心代码。
下面的代码展示了，从下标i开始做shiftUp操作
下面的代码展示了，从下标i开始做shiftDown操作
堆的heapfiy
从一个数组构建堆的操作，我们姑且称之为heapify。一种很容易想到的方法是，直接遍历数组push到一个空堆中，这种做法也有着不错的时间复杂度（O(NlogN)）。不过还有更优雅的做法，这种做法的时间复杂度是O(N)的。下面heapify代码非常简单，就是从数组中间向前遍历，依次做shiftDown操作，为什么要从size ÷ 2开始遍历呢？因为从这个下标开始往前的节点才有孩子节点，此时做shiftDown是有意义的。这个heapify操作的时间复杂度上界也是O(NlogN)的，不过渐渐时间复杂度是O(N)的，具体证明过程，大家可以参照《算法导论》。
堆的应用
堆是一种应用比较广泛的数据结构，在很多地方都有应用。下面我们就举两个Java中的例子。
- 优先级队列，普通的队列是先进先出，而优先级队列的出队总是优先级最高的元素，这很符合堆的特点。Java中提供的java.util.PriorityQueue和java.util.concurrent.PriorityBlockingQueue这两种优先级队列都是用堆实现的。
- Java定时任务线程池ScheduledThreadPoolExecutor中的工作队列DelayedWorkQueue其实也是一个堆的实现。