1. 堆的定义：
堆(Heap) - 也叫做优先队列(Priority Queue)；二叉堆是一个完全二叉树或近似完全二叉树。满足如下的两个属性:
1 父节点的键值总是大于或等于(小于或等于)它的任意一个子节点的键值(顺序性)；
2 堆总是一个完全二叉树；
将根节点最大的堆叫做最大堆；根节点最小的堆叫做最小堆；
2. 堆的存储：
可以采用数组来表示堆；我们使用下标1作为数组的开始；声明数组X[n + 1]，空出元素X[0]，根位于X[1]，它的两个子节点分别位于X[2]，X[3]，... ...
堆的典型定义如下(数组X满足如下条件)：
{
root 节点索引：1
left child(i) 当前节点i的左子节点索引：2 × i
right child(i) 当前节点i的右子节点索引：2×i + 1
parent(i) 当前节点i的父节点的索引值：i/2
}
示例如下：X[1, ... ... n]
3. 堆的操作：
两个关键的函数：siftup，siftdown：
3.1. siftup:
描述：现有数组X[1,... ..., n-1]为一个堆，插入一个新的元素在位置X[n]上，新的元素的键值可能小于其父节点，此时需将该节点向上调整，是X[1,... ... n]重新成为一个堆；
/**
* @param newItem the new inserted item
* @param n the current index in the array X for the newItem, initially it is the last index of the array + 1
*/
void siftup(T newItem, int n)
{
int currentIndex = n;
for (int parentIndex = ParentIndex(currentIndex); parentIndex > 0 && newItem < X[parentIndex]; )
{
X[currentIndex] = X[parentIndex];
currentIndex = parentIndex;
parentIndex = ParentIndex(parentIndex);
}
}
3.2. siftdown:
描述：现有数组X[1,... ...n]为一个堆,给X[1]分配一个新的值，重新调整使X重新满足堆的条件；
/**
* @param n the replaced node index, initially n = 1, replace the root node
* @param newItem the new replaced value on X[n]
*/
void siftdown(int n, T newItem)
{
int currentIndex = n;
// If current node owns child node(s), check
while (getLeftChildIndex(currentIndex) > heapSize)
{
int leftChildIndex = getLeftChildIndex(currentIndex);
int rightChildIndex = getRightChildIndex(currentIndex);
// get the index whose item value is the less one.
int minItemIndex = (rightChildIndex < heapSize) ? (X[leftChildIndex] < X[rightChildIndex] ? leftChildIndex : rightChildIndex) : (leftChildIndex);
if (newItem > X[minItemIndex])
{
X[currentIndex] = X[minItemIndex]; // swap value
currentIndex = minItemIndex;
}else
{
// exit
break;
}
}
X[currentIndex] = newItem;
}
3.3. 堆插入元素insert：
描述：每次插入都是将新数据放在数组的最后；然后向上调整使其重新满足堆条件；
void insert(T newItem)
{
siftUp(newItem, heapSize);
}
3.4. 堆删除元素delete:
描述：堆中每次只能删除根节点X[1]；为了便于重建堆，实际的操作是将最后一个数据的值赋给根节点，然后再向下调整，使其满足堆条件；
T delete()
{
T deletedItem = X[1];
heapSize -= 1;
siftdown(1, X[n]);
return deletedItem;
}
3.5. 堆排序：
描述：堆X[1, ... ... n]建好之后，X[1]为最小的元素；将X[1]取出，放在X[n]位置上，然后将原来的X[n]放在X[1]上，向下调整，得到新的堆X[1,... ... n - 1]；然后将新堆的X[1]放在X[n - 1]上，X[n - 1]放到X[1]上，siftdown得到新的堆X[1, ... ... n-2]；重复上面过程直到X[1]与X[2]交换为止；
void sort()
{
for (int i = n; i > 1; i--)
{
swap(X[1], X[i]);
heapSize -= 1; // reduce the heap size.
siftdown(1, X[1]); // current X[1] is the new value which is the X[i] before the swaption.
}
}
3.6. 堆操作的动态演示：
http://www.benfrederickson.com/2013/10/10/heap-visualization.html
4. C++ STL中的堆操作：