介绍

堆是一种数据结构，它是一颗完全二叉树。最大堆则是在堆的基础增加了新的规则，它的根结点的值是最大的，而且它的任意结点的父结点的值都大于或者等于其左右结点的值。

代码

把堆看做一颗树的数组对象，相对于任意的一个结点（i），它都满足以下3个特性，如果它存在左右结点的话，那么其左结点的位置就i*2，右结点就是i*2 +1,父结点就是i/2。

定义一个最大堆的模板类max_stack，默认它的初始大小为DEFAULT_SIZE=1024，采用c++中容器vector来代表堆（方便扩展），length_表示堆的长度。

当往堆里面插入一个数据时，先判断当前堆长度是否已经等于默认长度，如果等于，则把容器的长度扩大一倍。然后把数据插入到数组的最后一位，用heap_increase_key方法移动它的位置。

heap_increase_key方法表示把i的原来的值替换成t值。然后递归和它的父结点做比较，如果比父结点值大，则它的值就和父结点做交换，如果小于，则递归结束，当前的i值就是它的位置。

获取最大堆的最大值，就是返回它的根结点的值。

返回最大堆的最大值，并且删除最大值，则需要重新计算出当前堆的最大值。其中的max_heapify方法就是对某个结点求最大堆的过程。

max_heapify方法是对某个结点求最大堆的过程：首先求出当前结点的左右结点，并判断左右结点和当前结点中最大那个结点的值，如果当前结点不是最大的那个值，则把最大结点的值和当前结点的值进行交换，然后递归去判断交换以后的值和它的左右结点的值的大小，如果当前结点的值就是最大值，则递归结束。

build_max_heapify是一个建堆的过程，只需要对0-length/2调用max_heapify方法进行求最大堆的过程就可以了，因为length/2以后的都是子节点（由left,right方法可知），都会经过求最大堆的过程。

堆排序是建立在堆的基础上的，所以首先得建立一个堆，然后再排序。排序的过程：每次都把当前最小的结点和数组的末尾的结点值进行交换，交换完成以后减少堆的长度，然后对当前堆进行一个求最大堆的过程，又求出一个最大堆以后，重复刚刚动作，直至整个堆的结束。这样，一个倒序排序的数组就出来了，通过print函数就可以输出整个数组。

最大堆代码的测试用例：

总结

堆分2种，最大堆和最小堆，其实最小堆的实现和最大堆基本一样。最大堆的根是最大值，而最小堆的根是最小值，在某些判断上符号改变下就是最小堆了。最大堆的作用有很多，比如排序，比如事件驱动，某个需要判断整个数据当中，其中的最大值是否满足条件时，进行什么操作等等。需要了解更多的编程和算法问题，请关注我，谢谢。