堆可用于实现优先队列。
堆有两个性质：结构性和堆序性。
堆的结构性：
堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。
一棵高为h的完全二叉树有2^h～2^(h+1)-1个节点。这意味着，完全二叉树的高是logN下取整。
完全二叉树很有规律，可用一个数组表示而不需要指针。对于数组中任一位置i上的元素，其左儿子在2i上，右儿子在（2i+1）中，它的父亲则在位置i/2下取整上。（注：从数组下标1开始存放完全二叉树。）
堆的堆序性：
在一个堆中，对于每一个节点X，X的父亲中的关键字小于（或等于）X中的关键字，根节点除外（它没有父节点）。——这是最小堆，最小元在根上。
在一个堆中，对于每一个节点X，X的父亲中的关键字大于（或等于）X中的关键字，根节点除外（它没有父节点）。——这是最大堆，最大元在根上。
综上，我们可以用递归的方法定义堆：
（1）首先，堆是一个完全二叉树；
（2）其次，根上为最大（或最小）元素；
（3）最后，任意子树也是一个堆。
原文：http://www.cnblogs.com/nufangrensheng/p/3956917.html