一、何为“堆”
（一）基本概念
1、满二叉树
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是(2k) -1 ，则它就是满二叉树。如下图所示例子：
2、完全二叉树
完全二叉树的结点数是任意的，从形式上讲它是个缺失的的三角形，但所缺失的部分一定是右下角某个连续的部分，最后那一行可能不是完整的，对于k层的完全二叉树，结点数的范围2(k-1)-1 < N< 2k – 1；
设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。如下图所示例子：
有关二叉树的知识，小编并没有很系统的去总结，接下来也将做一个深入分享。
（二）堆的定义及其分类
1、 定义
堆（英语：heap)是计算机科学中一类特殊的数据结构的统称，是一颗完全二叉树，通常是一个可以被看做一棵树的数组对象。
堆是具有以下性质的完全二叉树：
（1）每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
（2）每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
2、二叉堆的分类
（1）大顶堆
大顶堆中，每个结点的值都大于其左孩子和右孩子结点的值。我们来画个图演示下：
（2）小顶堆
小顶堆中，每个结点的值都小于其左孩子和右孩子结点的值。同样给个例子如下：
（三）堆结点访问
通常堆是通过一维数组来实现的。在数组起始位置为0的情形中，父结点和子结点的位置关系如下：
（1）索引为i的左孩子的索引是 (2* i+1)
（2）索引为i的右孩子的索引是 (2* i+2)
（3）索引为i的父结点的索引是 (i -1)/2
注意：这里得到的关系由数组的起始位置来决定。小伙伴们可以对照上述大顶堆和小顶堆的图来分析分析索引的对应关系。
因此，在第一个元素的索引为0时：
对于大顶堆有：arr(i)>arr(2* i+1) && arr(i)>arr(2* i+2)
对于小顶堆有：arr(i)<arr(2* i+1) && arr(i)<arr(2* i+2)
二、构造初始堆（堆调整）
将无序数组构造成一个堆（升序用大顶堆，降序用小顶堆）。假设存在以下数组：
首先，我们找到当前这棵树的最后一个非叶子结点，对从该结点开始的所有非叶子结点进行结构判断，并依次进行调整。注意，这里是自底向上，从右至左对非叶子结点进行判断。但对于每个结点的调整而言，其实是向下调整。
（一）调整成大顶堆
第一步
找到最后一个非叶子结点为“数组长度/2-1=5/2-1=1【索引i=1】”，也就是上图中的结点36。，开始进行判断该子树是否满足堆的性质。
可以发现以该结点为根结点的子树不满足大顶堆的结构，找到子结点元素最大的那一个【两个子结点为arr[i* 2+1]与arr[i* 2+2]，也就是arr[3]与arr[4]】，进行调整，如下图所示：
第二步
继续找到上一个非叶子结点，也就是结点18【索引i=0】，按照相同方法进行调整。
结点调换之后，需要继续判断换下后的结点是否符合堆的特性【也就是以当前结点18为根的子树】。发现不符合，继续调整。此时结点18的索引i=1，从其左右孩子结点中选择最大的一个进行调换，结果如下：
第三步
发现没有非叶子结点了，这时调整结束。此时得到的就是最大堆。
仔细分析，发现可以通过一个外层的循环从最后一个非叶子结点开始进行遍历【所有非叶子结点】，注意这里非叶子结点的访问顺序是自底向上。循环体用来判断是否满足堆的性质来决定是否进行调整。每次进行调整时需要判断交换后的结点是否也满足堆的性质，不满足要继续进行同样的调整，这里是一个向下调整的过程。可以发现这其实是一个递归的过程【当然也可以采用迭代的方式实现】。因此代码设计上可以采用“循环+递归”或者“循环+迭代”的方法。
示例代码如下：
#include<iostream>
using namespace std;
/**
* 递归实现
* 调整索引为 index 处的数据，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化处理的数据的索引
* @param len 未排序的堆（数组）的长度
*/
void AdjustDown(int *arr, int index, int len)
{
int li = (index * 2) + 1; // 左子节点索引
int ri = li + 1; // 右子节点索引
int cMax = li; // 子节点值最大索引，默认左子节点。
// 左子节点索引超出计算范围，直接返回。
if (li > len)
{
return;
}
// 先判断左右子节点，哪个较大。
if (ri <= len && arr[li]<arr[ri])
{
cMax = ri;
}
//如果根结点小于叶子结点，交换
if (arr[index]<arr[cMax])
{
int item=arr[index];
arr[index]=arr[cMax];
arr[cMax]=item;
AdjustDown(arr, cMax, len); // 如果父节点被子节点调换，则需要继续判断换下后的父节点是否符合堆的特性。
}
}
/**
* 迭代实现
* 调整索引为 index 处的数据，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化处理的数据的索引
* @param len 未排序的堆（数组）的长度
*/
void maxHeapAdjust(int *arr, int index, int len)
{
int li = (index * 2) + 1; // 左子节点索引
int ri = li + 1; // 右子节点索引
int item=arr[index]; //存储该索引结点
while(li<len)
{
int cMax = li; // 子节点值最大索引，默认左子节点。
// 先判断左右子节点，哪个较大。
if (ri<=len && arr[li]<arr[ri])
{
cMax=ri;
}
//如果根结点小于叶子结点，交换
if (item>=arr[cMax])
{
break;
}
arr[li/2]=arr[cMax];//把子节点值赋值给父结点
li=cMax*2+1;//找到以cMax值为索引的结点的左孩子结点
ri=li+1;
}
arr[li/2]=item; //找到正确位置赋值
}
int main()
{
int len=15;
int arr[len]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
int maxIndex = len - 1; //最大索引
int beginIndex = len/ 2 - 1; //最后一个非叶子结点索引
/*
* 将数组堆化
* beginIndex = 第一个非叶子节点。
* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
* 循环遍历
*/
for (int i = beginIndex; i >= 0; i--)
{
//maxHeapAdjust(arr, i, maxIndex);
AdjustDown(arr, i, maxIndex);
}
for(int i=0;i<len;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
（二）调整成小顶堆
我们来把上述得到的最大堆来调整成最小堆。也就是下图：
第一步
找到最后一个非叶子结点为“数组长度/2-1=5/2-1=1【索引i=1】”，也就是上图中的结点40。，开始进行判断该子树是否满足堆的性质。
可以发现以该结点为根结点的子树不满足最小堆的结构，找到子结点元素最小的那一个【两个子结点为arr[i* 2+1]与arr[i* 2+2]，也就是arr[3]与arr[4]】，进行调整，如下图所示：
第二步
继续找到上一个非叶子结点，也就是结点47【索引i=0】，按照相同方法进行调整。
第三步
发现没有非叶子结点了，这时调整结束。此时得到的就是最大堆。
代码设计逻辑基本上是一样的。
示例代码
#include<iostream>
using namespace std;
/**
* 递归实现
* 调整索引为 index 处的数据，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化处理的数据的索引
* @param len 未排序的堆（数组）的长度
*/
void AdjustDown(int *arr, int index, int len)
{
int li = (index * 2) + 1; // 左子节点索引
int ri = li + 1; // 右子节点索引
int cMax = li; // 子节点值最大索引，默认左子节点。
// 左子节点索引超出计算范围，直接返回。
if (li > len)
{
return;
}
// 先判断左右子节点，哪个较小。
if (ri <= len && arr[ri]<arr[li])
{
cMax = ri;
}
//如果根结点大于叶子结点，交换
if (arr[index]>arr[cMax])
{
int item=arr[index];
arr[index]=arr[cMax];
arr[cMax]=item;
AdjustDown(arr, cMax, len); // 如果父节点被子节点调换，则需要继续判断换下后的父节点是否符合堆的特性。
}
}
/**
* 迭代实现
* 调整索引为 index 处的数据，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化处理的数据的索引
* @param len 未排序的堆（数组）的长度
*/
void maxHeapAdjust(int *arr, int index, int len)
{
int li = (index * 2) + 1; // 左子节点索引
int ri = li + 1; // 右子节点索引
int item=arr[index]; //存储该索引结点
while(li<len)
{
int cMax = li; // 子节点值最大索引，默认左子节点。
// 先判断左右子节点，哪个较小。
if (ri<=len && arr[ri]<arr[li])
{
cMax=ri;
}
//如果根结点小于叶子结点，交换
if (item<arr[cMax])
{
break;
}
arr[li/2]=arr[cMax];//把子节点值赋值给父结点
li=cMax*2+1;//找到以cMax值为索引的结点的左孩子结点
ri=li+1;
}
arr[li/2]=item; //找到正确位置赋值
}
int main()
{
int len=5;
int arr[len]={47,40,45,18,36};
int maxIndex = len - 1; //最大索引
int beginIndex = len/ 2 - 1; //最后一个非叶子结点索引
/*
* 将数组堆化
* beginIndex = 第一个非叶子节点。
* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最小。
* 循环遍历
*/
for (int i = beginIndex; i >= 0; i--)
{
//maxHeapAdjust(arr, i, maxIndex);
AdjustDown(arr, i, maxIndex);
}
for(int i=0;i<len;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
(三)时间复杂度分析
假设二叉树的高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；高层也是这样逐渐递归。
小编来分析下这个时间复杂度求解的过程。
1、n为结点的个数，树的高度（即堆的高度）为h【树的高度与深度相等】
2、由于是自底向上，从右至左调整构建堆，因此在调整上层元素的时候，并不需要同下层所有元素进行比较，只需要同其中一个分支进行比较，而做比较的次数则是树的高度减去当前结点的高度。第i层上结点元素的个数为2(i-1)，(h-i)表示每个结点要比较的次数。因此，第i层所有结点的总比较次数为T(i)=2(i-1) * (h-i)。
3、因此，总的计算时间：
S=T(h-1)+T(h-2)+……+T(1)=2(h-2)* 1+2(h-3)* 2+……+(h-1)
注意：因为叶子层不用交换，所以i从h-1开始到1，第一个非叶子结点所在层所有结点的高度都为1。
可以发现该数列为等差数列和等比数列的乘积，利用错位相减法可进行解决。
2S=2(T(h-1)+T(h-2)+……T(1))=2(h-1)* 1+2(h-2)* 2+……+2* (h-1)
2S-S=2(h-1)+2(h-2)+2(h-3)+……+2-(h-1)
除最后一项外，这就是个等比数列，直接用上求和公式：
Sn=a1* (1-qn)/(1-q)(q≠1)
得到：S=2h-h-1
因为h为完全二叉树的高度，因此有：2(h-1)<n<2h，总之可以认为：h=logn （实际计算得到应该是 log2n+1 < h <= log2n ）;
综上所述得到：S = n - logn -1
所以时间复杂度为：O(n)（堆的初始化过程）。
三、堆元素的插入
刚已经分析了堆的初始化过程，那接下来我们来探究下，怎样往一个堆里面去插入数据。
（一）基本插入过程
堆的插入操作是自底向上进行的【这里指每个结点是向上进行调整】，每次从堆的最后一个结点开始插入（将插入的值放入完全二叉树的最后一个结点），为了维持堆的性质，还要从插入结点开始依次往前递归，去维持堆的三个特性。
取插入结点的父节点，比较父节点的值和插入结点的值，将较小的值交换到父节点位置。再以父节点为当前结点，重复上一步操作，直到遇到父节点比插入结点值小，就可以结束递归。
（二）实例分析
这里仅以大顶堆作为例子讲解，用的还是上述得到的大顶堆，我们来往堆里插入新的元素。
我们现在有这样的三个数46、70、50等待我们插入，一起来分析下。
插入46：
得到下图：
插入70
得到下图：
发现交换后的结点70已经是根节点，那么本次插入到此结束。
插入50：
得到下图：
取插入结点50的父节点18，比较父节点的值和插入结点的值，发现不满足最大堆的性质，将较大的值交换到父节点位置。重复相同的操作，最终得到下图：
（三）代码示例
根据上述分析，可得到代码如下：
//迭代
bool Heap<T>::insert(const T& val)
{
/*
最大堆特点是根结点比子节点都大
根据该性质进行调整
(1)索引为i的左孩子的索引是 (2i+1)
（2）索引为i的右孩子的索引是 (2i+2)
（3）索引为i的父结点的索引是 (i-1)/2
*/
int i=len++;
while(i>0 && heap[(i-1)/2]<val)
{
heap[i]=heap[(i-1)/2];
i=(i-1)/2;
}
heap[i]=val;
return true;
}
//递归
template<typename T>
void Heap<T>::AdjustUp(const T& val)
{
int i=len++;
AdjustUps(val,i);
}
template<typename T>
void Heap<T>::AdjustUps(const T& val,int i)
{
if(i<0)
{
return;
}
if(heap[(i-1)/2]<val)
{
heap[i]=heap[(i-1)/2];
heap[(i-1)/2]=val;
i=(i-1)/2;
AdjustUps(val,i);
}
}
（四）时间复杂度分析
我们可以看到，每个结点的插入都和树的深度有关，并且都是不断的把树折半来实现插入，因此是典型的递归【当然用迭代法也可实现，道理一样】。
插入一个新的结点后树的结点数为n，高度为h，那么此时结点要交换的最多次数为：S=h-1
因为h为完全二叉树的高度，因此有：2(h-1)<n<2h，总之可以认为：h=logn （实际计算得到应该是 log2n+1< h < log2n ）;
所以S=O(logn)-1
插入的时间复杂度为O(logn)。
四、堆元素的查找
堆元素的查找相对还是比较简单，对于一颗满二叉树来说，n个节点的二叉排序树的高度为log2(n+1),其查找效率为O(log2n)，也就是O(logn)，近似于折半查找。
同样，查找可以有迭代和递归两种实现方法，代码如下所示：
//非递归实现
template<typename T>
int Heap<T>::search(const T& val)
{
int i=0;
while(i<len)
{
if(heap[i]==val)
{
return i;
}
if(heap[2*i+1]==val)
{
return 2*i+1;
}
if(heap[2*i+2]==val)
{
return 2*i+2;
}
i++;
}
}
//递归实现
template<typename T>
int Heap<T>::find(const T& val)
{
_find(val,0);
}
template<typename T>
int Heap<T>::_find(const T& val,int i)
{
if(heap[i]==val)
{
return i;
}
if(heap[2*i+1]==val)
{
return 2*i+1;
}
if(heap[2*i+2]==val)
{
return 2*i+2;
}
_find(val,i++);
}
五、堆元素的删除
接下来我们来关注下堆里元素的删除。我们还是以下图作为例子来看看怎么进行删除【大顶堆】。
首先找到结点50对应位置的索引,把当前堆的最后一个结点的值赋到当前位置，然后删除最后一个结点，堆的当前长度减1。得到下图：
那么接下来就是对当前结点18进行调整。调整的方式与上述一致。这里只放个图片：
因此对于堆里元素的删除，基本过程就是：
（1）找到待删除元素的位置索引
（2）将堆的最后一个元素赋值到该位置上，堆的容量减1
（3）进行堆结构的调整
代码如下所示：
template<typename T>
bool Heap<T>::deletes(const T& val)
{
int i=search(val);
heap[i]=heap[len-1];
len--;
AdjustDown(heap,i);
//maxHeapAdjust(heap,i);
}
六、堆排序
（一）基本思想
1、将待排序序列构造成一个大顶堆【小顶堆】，此时，整个序列的最大值【最小值】就是堆顶的根节点。
2、将其与末尾元素进行交换，此时末尾就为最大值【最小值】。
3、然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值【次大值】。如此反复执行，便能得到一个有序序列了。
注意：降序排序使用大顶堆，升序排序使用小顶堆。
（二）基本步骤
1、构造初始堆
小编前面已经分析了大顶堆与小顶堆的各种有关操作。所以这里构造初始堆的步骤不再做解释。堆创建成功之后，接下来就是堆的调整使最后的数组有序。
2、调整堆
这里小编仅以大顶堆作为例子。将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。小编用上述得到的大顶堆来进行演示，也就是下图：
1、将堆顶元素47和末尾元素36进行交换
重新调整结构，使其继续满足堆定义，得到下图：
2、再将堆顶元素45与末尾元素18进行交换，得到下图：
重新调整结构，使其继续满足堆定义，得到下图：
（三）时间复杂度分析
调整堆的复杂度计算和初始化堆差不多，都为O(logn)。又因为堆排序每个结点都要进行一次调整，因此堆排序的总时间复杂度为O(nlogn)。
（四）示例代码
小编自己写了大顶堆的相关操作代码，包括创建，堆化、查找、删除、排序等等。小顶堆这里不做分享，原理一样的。代码如下所示：
#include <stdio.h>
#include <iostream>
using namespace std;
/*
本程序中堆的起始索引为0
*/
// 堆的实现,二叉树用数组来表示
template<typename T>
class Heap
{
public:
Heap(const int& size); //创建堆
~Heap();
bool insert(const T& val); //堆插入非递归
bool deletes(const T& val);//堆删除非递归
void AdjustUp(const T& val);//堆插入调整
void AdjustUps(const T& val,int i);//向上调整
void Delete(const T& val); //删除堆中某个数
int search(const T& val); //迭代查找堆中某个数所在位置
int find(const T& val); //递归查找堆中某个数所在位置
int _find(const T& val,int i); //递归查找堆中某个数所在位置
void AdjustDown(T* arr, int index) ;//递归调整最大堆 ---向下调整
void maxHeapAdjust(T* arr, int index) ;//迭代调整最大堆
void ArrToHeap(T* arr); //数组转换为堆
void AdjustToHeap(T* arr,int arrlength) ;//将数组元素拷贝到堆中再进行调整，调整后的heap支持插入删除等操作
void HeapSort(); //大顶堆排序，升序，最大值放最后位置
void ArrToHeapToSort(T* arr); //传入数组转换成堆进行排序
void print(); //打印堆元素
private:
T* heap; //堆
int MaxSize,len,temp; //MaxSize为堆最大容量，Nel为堆目前元素个数,
};
template<typename T>
Heap<T>::Heap(const int& size)
{
MaxSize = 2*size;
heap =new T[MaxSize];
len=size;
}
template<typename T>
Heap<T>::~Heap()
{
delete []heap;
heap = NULL;
MaxSize = 0;
}
/**
* 递归实现
* 调整索引为 index 处的数据，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化处理的数据的索引
* @param len 未排序的堆（数组）的长度
*/
template<typename T>
void Heap<T>::AdjustDown(T* arr, int index)
{
int li = (index * 2) + 1; // 左子节点索引
int ri = li + 1; // 右子节点索引
int cMax = li; // 子节点值最大索引，默认左子节点。
int maxIndex = len - 1; //最大索引
// 左子节点索引超出计算范围，直接返回。
if (li > maxIndex)
{
return;
}
// 先判断左右子节点，哪个较大。
if (ri <= maxIndex && arr[li]<arr[ri])
{
cMax = ri;
}
//如果根结点小于叶子结点，交换
if (arr[index]<arr[cMax])
{
int item=arr[index];
arr[index]=arr[cMax];
arr[cMax]=item;
AdjustDown(arr, cMax); // 如果父节点被子节点调换，则需要继续判断换下后的父节点是否符合堆的特性。
}
}
/**
* 迭代实现
* 调整索引为 index 处的数据，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化处理的数据的索引
* @param len 未排序的堆（数组）的长度
*/
template<typename T>
void Heap<T>::maxHeapAdjust(T* arr, int index)
{
int li = (index * 2) + 1; // 左子节点索引
int ri = li + 1; // 右子节点索引
int item=arr[index]; //存储该索引结点
int maxIndex = len - 1; //最大索引
while(li<maxIndex)
{
int cMax = li; // 子节点值最大索引，默认左子节点。
// 先判断左右子节点，哪个较大。
if (ri<=maxIndex && arr[li]<arr[ri])
{
cMax=ri;
}
//如果根结点小于叶子结点，交换
if (item>=arr[cMax])
{
break;
}
arr[li/2]=arr[cMax];//把子节点值赋值给父结点
li=cMax*2+1;//找到以cMax值为索引的结点的左孩子结点
ri=li+1;
}
arr[li/2]=item; //找到正确位置赋值
}
/*
将数组调整为堆
*/
template<typename T>
void Heap<T>::ArrToHeap(T* arr)
{
int beginIndex = len/ 2 - 1; //最后一个非叶子结点索引
/*
* 将数组堆化
* beginIndex = 第一个非叶子节点。
* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
* 循环遍历
*/
for (int i = beginIndex; i >= 0; i--)
{
maxHeapAdjust(arr, i);
// AdjustDown(arr, i);
}
}
/*
将数组元素拷贝到heap数组中再进行调整
调整后的heap支持插入删除等操作
*/
template<typename T>
void Heap<T>:: AdjustToHeap(T* arr,int arrlength)
{
for(int i=0;i<arrlength;i++)
{
heap[i]=arr[i];
}
int beginIndex = len/ 2 - 1; //最后一个非叶子结点索引
/*
* 将数组堆化
* beginIndex = 第一个非叶子节点。
* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
* 循环遍历
*/
for (int i = beginIndex; i >= 0; i--)
{
maxHeapAdjust(heap, i);
// AdjustDown(arr, i);
}
}
template<typename T>
bool Heap<T>::insert(const T& val)
{
/*
最大堆特点是根结点比子节点都大
根据该性质进行调整
(1)索引为i的左孩子的索引是 (2i+1)
（2）索引为i的右孩子的索引是 (2i+2)
（3）索引为i的父结点的索引是 (i-1)/2
*/
int i=len++;
while(i>0 && heap[(i-1)/2]<val)
{
heap[i]=heap[(i-1)/2];
i=(i-1)/2;
}
heap[i]=val;
return true;
}
template<typename T>
void Heap<T>::AdjustUp(const T& val)
{
int i=len++;
AdjustUps(val,i);
}
template<typename T>
void Heap<T>::AdjustUps(const T& val,int i)
{
if(i<0)
{
return;
}
if(heap[(i-1)/2]<val)
{
heap[i]=heap[(i-1)/2];
heap[(i-1)/2]=val;
i=(i-1)/2;
AdjustUps(val,i);
}
}
//非递归实现
template<typename T>
int Heap<T>::search(const T& val)
{
int i=0;
while(i<len)
{
if(heap[i]==val)
{
return i;
}
if(heap[2*i+1]==val)
{
return 2*i+1;
}
if(heap[2*i+2]==val)
{
return 2*i+2;
}
i++;
}
}
//递归实现
template<typename T>
int Heap<T>::find(const T& val)
{
_find(val,0);
}
template<typename T>
int Heap<T>::_find(const T& val,int i)
{
if(heap[i]==val)
{
return i;
}
if(heap[2*i+1]==val)
{
return 2*i+1;
}
if(heap[2*i+2]==val)
{
return 2*i+2;
}
_find(val,i++);
}
template<typename T>
bool Heap<T>::deletes(const T& val)
{
int i=search(val);
heap[i]=heap[len-1];
len--;
AdjustDown(heap,i);
//maxHeapAdjust(heap,i);
}
template<typename T>
void Heap<T>::HeapSort()
{
int index=len-1;
int tmplen=len;
while(index>=0)
{
int tmp=heap[index];
heap[index]=heap[0];
heap[0]=tmp;
len--;
index--;
AdjustDown(heap,0);
}
len=tmplen;
}
template<typename T>
void Heap<T>::ArrToHeapToSort(T* arr)
{
ArrToHeap(arr);
int index=len-1;
int tmplen=len;
while(index>=0)
{
int tmp=arr[index];
arr[index]=arr[0];
arr[0]=tmp;
len--;
index--;
AdjustDown(arr,0);
}
len=tmplen;//恢复堆长度
for(int i=0;i<len;i++)
{
cout<<arr[i]<<" ";
}
}
template<typename T>
void Heap<T>::print()
{
for(int i=0;i<len;i++)
{
cout<<heap[i]<<" ";
}
}
int main()
{
int arr[5]={18,36,45,40,47};
int arrlength=sizeof(arr)/sizeof(arr[0]);
Heap<int> max_heap(arrlength);
//max_heap.ArrToHeapToSort(arr);
max_heap.AdjustToHeap(arr,arrlength);
//max_heap.HeapSort();
max_heap.AdjustUp(46);
max_heap.AdjustUp(70);
max_heap.AdjustUp(50);
//cout<<max_heap.search(50)<<endl;
cout<<max_heap.find(50)<<endl;
//max_heap.insert(46);
//max_heap.deletes(50);
max_heap.print();
return 0;
}
七、堆应用之“优先级队列”
（一）队列与优先队列的区别
1、队列是一种FIFO（First-In-First-Out）先进先出的数据结构，对应于生活中的排队的场景，排在前面的人总是先通过，依次进行。
2、优先队列是特殊的队列，从“优先”一词，可看出有“插队现象”。比如在火车站排队进站时，就会有些比较急的人来插队，他们就在前面先通过验票。优先队列至少含有两种操作的数据结构：insert（插入），即将元素插入到优先队列中（入队）；以及deleteMin（删除最小者），它的作用是找出、删除优先队列中的最小的元素（出队）。
3、优先队列的实现常选用二叉堆，在数据结构中，优先队列一般也是指堆。
（二）C++优先队列简介
优先队列在头文件#include <queue>中；其声明格式为：priority_queue <int> q;【声明一个名为q的整形的优先队列】。
支持的操作:
q.empty() //如果队列为空，则返回true，否则返回false
q.size() //返回队列中元素的个数
q.pop() //删除队首元素，但不返回其值
q.top() //返回具有最高优先级的元素值，但不删除该元素
q.push(item) //在基于优先级的适当位置插入新元素
有关操作不做介绍了。
八、一点总结
堆的使用场景还是非常丰富的，掌握堆的各种操作很有必要。啰里啰唆写了一大堆，或多或少存在些错误，也请指正，谢谢！
