二叉堆是一种典型的优先队列实现策略，广义而言，堆是优先队列的实现方式，在此之下又分为二叉堆，左式堆，斜堆，二项队列等具体形态。但第一个用得太普遍了，所以我们平时一说到堆(Heap)指的就是二叉堆。基本模型如下，基本操作就这两个，其他的是扩展。
以后我们讨论的堆，如果不特殊说明，那都以小顶堆为例，堆顶元素为最小的值，但优先级上却是最高的。我们从二叉堆的起源谈起，如何根据之前已经掌握的数据结构来实现优先级队列，在这里，既要考虑效率还要兼顾成本，那最佳的实现方式应该是这两个因素的综合与兼顾，这就要求我们设计模型的时候发挥统筹兼顾、总揽全局的领导核心作用。
第一种实现方式是基于此前的向量或链表，这样的话，实现方便而且能保证某种情况下的效率。它可以在表头以$O\left( 1 \right)$的时间插入元素，如果要查询最小元素，那需要耗费$\Theta \left( N \right)$时间。如果删除最小元素，不仅要遍历整个表来查到优先级最小的，而且需要在摘除之后将它的所有后继顺次前移，两项工作的成本累计$\Theta(n)+O(N)=\theta(N)$。这就有点慢了，那另一种方法就是始终让表保持有序，构成有序向量，这往往会让算法性能有实质提高。这时候查找和删除最小元素只需要$O\left( 1 \right)$时间，如果要插入一个元素，我们要先找到他所在的位置，花费$O\left( N \right)$,然后将它的所有后继元素后移一个单位留出空位，在最坏和平均情况都需要耗费$O\left( N \right)$，所以总代价是$O\left( N \right)$。因此将向量有序化也不是一个行之有效的策略。
同样，借助链表也不能高效地实现优先级队列。
以上方法都各有缺陷，那或许我们会求诸之前学过的BBST，没错，无论是用AVL树、伸展树或者红黑树实现优先队列，三个标准接口（增、删、查）的效率都可以达到$O\left( \log n \right)$，而且只需作一点优化，其中的getMin()接口效率还可以进一步提高到$O\left( 1 \right)$。但是就优先队列所要求的功能来说，BBST的功能就过于强大了。因为我们在优先队列里查找和删除都仅限于堆顶，而难以找到某个确切元素，并没有完全用上BBST的完整功能。也就是说，我们实际上是使用了一个非常高级的数据结构来实现一个功能更为简单的结构，而且BBST的开销也是比较大的，这简直杀鸡用牛刀。那有没有成本更低的实现方式呢？我们注意到对于优先队列而言，矛盾都集中在优先级最高的那个极值元素。这就意味着，我们只需要维护所有元素之间的一个偏序关系，就足以确定这个极值元素，而不必像BBST那样，始终都不折不扣地维护一个所有元素之间的全序关系。根据这一分析，我们确信一定存在某种形式上更简单，而且维护成本更低的实现方式。
总结一下：采用基本的向量结构不够，而采用更高级的树形结构，却有杀鸡用牛刀之嫌。我们要找一个中庸之道，为此我们需要以向量为形，以树形结构为神，形成二者之间的有机结合。就是逻辑上用树组织，但物理上用数组实现。为此，我们需要借助完全二叉树，可以认为是AVL树的一个特例，它的平衡因子处处非负，这也是二叉堆名字的来由。
和BST一样，堆也有两个性质：结构性和堆序性。如同AVL树一样，对堆的任何一次操作都有可能破坏这些性质，所以我们要时时维护这两个性质。下面来仔细分析一下这两个性质究竟为何物。
结构性质
堆是一颗被完全填满的二叉树，底层可能有空缺，但至少要保证从左到右填充，这样的树被称为完全二叉树（complete binary tree）。比如这样