堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。


最大堆：每个父节点的都大于孩子节点。

最小堆：每个父节点的都小于孩子节点。


堆结构的二叉树存储是：


代码实现如下：

#pragmaonce#include<iostream>#include<vector>#include<assert.h>usingnamespacestd;//仿函数template<typenameT>structGreater{booloperator()(constT&l,constT&r){returnl>r;}};template<typenameT>structLess{booloperator()(constT&l,constT&r){returnl<r;}};//模板参数template<typenameT,typenamecomer=Greater<T>>classHeap{public://无参构造函数Heap():_a(NULL){}//有参构造函数Heap(T*a,size_tsize){assert(a);//先把数据保存在vector中for(size_ti=0;i<size;i++){_a.push_back(a[i]);}//建堆for(intj=((_a.size()-2)/2);j>=0;j--){//向下调整算法_AdjustDown(j);}}voidPush(constTx)//插入元素{_a.push_back(x);_AdjustUp(_a.size()-1);}voidPop()//删除元素{assert(_a.size()>0);swap(_a[0],_a[_a.size()-1]);_a.pop_back();_AdjustDown(0);}size_tSize(){return_a.size();}boolEmpty(){return_a.empty();}voidprint(){for(inti=0;i<_a.size();i++){cout<<_a[i]<<"";}cout<<endl;}protected://向下调整算法void_AdjustDown(size_tparent){size_tchild=parent*2+1;comercom;while(child<_a.size()){//找出左右孩子中比较大的if(child+1<_a.size()&&com(_a[child+1],_a[child])){child++;}//比较父亲和孩子的大小if(com(_a[child],_a[parent])){swap(_a[child],_a[parent]);parent=child;child=parent*2+1;}else{break;}}}//向上调整算法void_AdjustUp(size_tchild){assert(child<_a.size());intparent=(child-1)/2;comercom;while(child>0){//只需看父节点<根节点if(com(_a[child],_a[parent])){swap(_a[child],_a[parent]);child=parent;parent=(child-1)/2;}else{break;}}}private:vector<T>_a;};

需要学习的也就是向上以及向下调整算法。

欢迎大家提出宝贵的意见。

测试用例如下：

voidTest(){inta[]={10,11,13,12,16,18,15,17,14,19};Heap<int,Less<int>>hp1(a,sizeof(a)/sizeof(a[0]));hp1.print();cout<<hp1.Size()<<endl;cout<<hp1.Empty()<<endl;hp1.Push(20);hp1.print();cout<<hp1.Size()<<endl;cout<<hp1.Empty()<<endl;hp1.Pop();hp1.print();cout<<hp1.Size()<<endl;cout<<hp1.Empty()<<endl;