堆是一种特殊的数据结构，它通常是一个可以被看做一棵树的数组对象。
What？那它到底是一棵树，还是一个数组呢？答案是数组。这个数组以二叉树的形式来维护。注意：这个二叉树必须是完全二叉树
堆结构的二叉树存储有两种：
最大堆：每个父亲结点的值都大于孩子结点。
最小堆：每个父亲结点的值都小于孩子结点。
顾名思义，这种结构就是可以根节点为最大的/最小的结点。不过有一点要注意，堆内的元素并不一定是按数组下标来排序的，很多
初学者会错误的认为最大/最小堆中下标为1的就是第一大/小，下标为2的就是第二大/小。。。。。。
你会问，堆既然是一个数组，那么它如何以二叉树的形式来保存呢？——————答案：下标。
我们先来看一棵二叉树的模型：（这是一棵乱序的完全二叉树）红色数字代表结点的值，黑色数字代表结点的下标。
以上，我们可以看出，每个根结点的下标 = （（左/右）孩子结点下标-1）/2，左孩子结点下标 = （根结点*2）+1，右孩子结点下
标 = （根结点*2）+ 2。这样我们用数组以下标
方式就可以很好的存储一颗树了（前提是这棵树必须是完全二叉树），我们就会得到一个数组 int a [] = {10,16, 18, 12, 11, 13, 15, 17, 14, 19};
下面我开始讲如何建立并维护一个堆，以最大堆为例。
假设，我们现在已经有了一个乱序的堆(例上图)，如何让它变成最大堆/最小堆呢？————堆的向下调整，向上调整。
向下调整：（调整根结点parent）
我们先要找到数组中存放的最后一个非叶子结点parent（上图中的下标为4值为11的结点）。找出它的左孩子leftchild和右孩rightchild
的最大值MaxChild，与父结点parent进行比较，若MaxChild>parent，则将它们俩的值进行交换。然后令parent的下标 = MaxChild下
标。再重复之前的操作。直到leftChild >= 数组的size。
到这里，我们才完成了一次向下调整，并不足以构成一个最大堆，在向下调整函数外面我们需要加上一个循环，每次向向下调整函数
传入想调整的根结点。（最后一个非叶子结点只是一个循环的‘起点’）
下面看代码：
template<typename T>
class Heap
{
public:
//建堆
Heap(const T* a, int sz)
{
_a.resize(sz);
for (int i = 0; i < sz; i++)
{
_a[i] = a[i];
}
for (int i = (_a.size() - 2) / 2; i >= 0; i--)//外层循环，每次传入根结点下标。（_a.size()-2）/2即为最后一个非叶子结点下标。
{
AdjustDown(i);
}
}
protected:
//向下调整
void AdjustDown(int root)
{
int parent = root;
size_t child = parent * 2 + 1;
while (child < _a.size())//当child>=_a.size()的时候，说明已经越界。
{
if (child + 1 < _a.size() && _a[child + 1] > _a[child])
{
child++;
}
if (_a[child] > _a[parent])
{
swap(_a[child], _a[parent]);//交换child与parent
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
protected:
vector<T> _a;//用Vector来代替一个数组
};
再来看向上调整，就简单的多了。找到你想调整的结点child，找出它的父亲结点parent，比较两个的大小，若child < parent，不操
作。若child > parent, 则交换两个的值，然后令child的下标 = parent的下标。重复以上操作，直到child的下标 <= 0(说明到达根结点)。
代码：
//向上调整
void AdjustUp(int root)
{
int child = root;
int parent = (child - 1) / 2;
Compare com;
while (child > 0)
{
if (!com(_a[child] ,_a[parent]))
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
依靠上面两个算法，我们就可以建立一个最大堆了，下面我再来讲两个维护堆的算法。
Push插入
每次都插到数组最后，然后针对这个结点进行一次向上调整。
//插入
void Push(const T& x)
{
_a.push_back(x);
AdjustUp(_a.size() - 1);
}
Pop删除（删除根结点，即数组第一个元素）
有人可能会想，直接让数组向前挪动一位就行了。错！，如果你这么做，确实达到了删除的效果，但是你破坏了整个堆的结构。
正确的做法是将根结点（第一个元素）与最后一个结点（最后一个元素）进行交换，删除最后一个元素，然后再根结点进行一次向下调整。
//删除
void Pop()
{
assert(!_a.empty());
swap(_a[0], _a[_a.size() - 1]);
_a.pop_back();
AdjustDown(0);
}
堆有什么应用？
1、堆排序，时间复杂度为O（N*lgN），最大堆，从小到大排序。最小堆，从大到小排序。
2、优先级队列。
3、大数据筛选，一个文件中包含了1亿个随机数，如何快速找到最大（小）的100W个数字（时间复杂度为O(N*lgk)）。
【解析】取前100 万个整数，构造成了一棵数组方式存储的具有小顶堆，然后接着依次取下一个整数，如果它大于最小元素亦即堆顶元素，则将其赋予堆顶元素，然后用Heapify调整整个堆，如此下去，则最后留在堆中的100万个整数即为所求 100万个数字。该方法可大大节约内存。
堆