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

堆结构的二叉树存储：

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

建堆：由于堆被视为完全二叉树，故在h-1层找到第一个（从后往前找）非叶子结点，进行堆的下调

建大堆时，从下往上依次判断并调整堆，使该结点的左右子树都满足大堆

建小堆时，从下往上依次判断并调整堆，使该结点的左右子树都满足小堆

可见大堆的建立与小堆的建立方式类似，下面以大堆进行讨论。

利用vactor模板存储堆中元素

template<classT>classHeap{public:Heap();Heap(constT*a,size_tsize);voidPush(constT&x);voidPop();T&GetTop();//访问堆顶元素boolEmpty();//判空size_tSize();//堆元素个数voidPrintHeap();protected:void_AdjustDown(size_tParent);//下调--建大堆(每个父结点都大于孩子结点)void_AdjustUp(size_tChild);//上调--建小堆(每个父结点都小于孩子结点)private:vector<T>_a;};

实现堆的建立

template<classT>Heap<T>::Heap():_a(NULL){}template<classT>Heap<T>::Heap(constT*a,size_tsize){assert(a);_a.reserve(size);//初始化_a(vector模板的使用)for(size_ti=0;i<size;++i){_a.push_back(a[i]);}////堆的第一个非叶子结点的数组下标时((size-1)-1)/2（最后一个结点是size-1）for(inti=(int)(size-2)/2;i>=0;--i)//不能定义为size_t（无符号）{_AdjustDown(i);}//建小堆，类似建大堆的方式，从下向上进行调整堆，使该结点处的左右子树都满足小堆//在进行调小堆时，也通过下调实现}//下调--建大堆/小堆template<classT>voidHeap<T>::_AdjustDown(size_tParent){size_tChild=Parent*2+1;while(Child<_a.size()){//先进行左右结点的比较,使Child为较大的数的下标，然后与父亲结点进行比较，使较大的数据为父亲结点if(Child+1<_a.size()&&_a[Child]<_a[Child+1])//存在右结点再进行比较{++Child;}if(_a[Child]>_a[Parent])//如果子结点大于父亲结点就交换，否则就要跳出循环{swap(_a[Child],_a[Parent]);Parent=Child;Child=Parent*2+1;}else{break;}}}//在建立小堆时，只需要将比较条件进行改变就可以实现

在已经是大堆或小堆的堆中加入元素使堆仍为大堆，可通过该元素与它的父结点进行比较

ps：由于插入的元素在数组末尾，故需要通过上调进行比较实现堆的大堆或小堆

template<classT>voidHeap<T>::_AdjustUp(size_tChild)//上调{size_tParent=(Child-1)/2;//结点为Child的父亲结点为（Child-1）/2while(Child>0)//当Child等于0时以到堆顶，终止循环{if(_a[Parent]<_a[Child])//直接进行父亲结点和子结点的比较{swap(_a[Child],_a[Parent]);Child=Parent;Parent=(Child-1)/2;}else{break;}}}template<classT>voidHeap<T>::Push(constT&x)//元素x入堆{//_a.resize(_a.size()+1);//_a[_a.size()-1]=x;_a.push_back(x);_AdjustUp(_a.size()-1);}

堆中pop元素，删除堆顶元素，使堆仍为大堆。

在已经是大堆或小堆的堆中删除堆顶元素，直接删除堆顶元素，造成无法进行大堆或小堆的实现，可通过将第一个元素与最后一个元素进行交换，然后删除最后一个元素，最后通过下调实现大堆或小堆

template<classT>voidHeap<T>::Pop()//出堆{size_tsize=_a.size();assert(size>0);//断言堆非空swap(_a[0],_a[size-1]);_a.pop_back();_AdjustDown(0);//从堆顶开始进行下调}

实现堆的堆顶，判空及堆元素个数

template<classT>T&Heap<T>::GetTop()//访问堆顶元素{return_a[0];}template<classT>boolHeap<T>::Empty()//判空{return_a.size()==0;}template<classT>size_tHeap<T>::Size()//堆元素个数{return_a.size();}template<classT>voidHeap<T>::PrintHeap(){for(size_ti=0;i<_a.size();++i){cout<<_a[i]<<"";}cout<<endl;}

测试用例

#include"Heap.hpp"voidTest4(){intarr[]={10,16,18,12,11,13,15,17,14,19};Heap<int>h(arr,sizeof(arr)/sizeof(arr[0]));h.PrintHeap();cout<<"empty:"<<h.Empty()<<endl;cout<<"size:"<<h.Size()<<endl;cout<<"gettop:"<<h.GetTop()<<endl;h.Push(20);h.PrintHeap();h.Pop();h.PrintHeap();}

如果对于上述说明还是不是很清楚，可自己亲手画图分析，存在不足之处请多多指教。

【vector】包含着一系列连续存储的元素, 其行为和数组类似。访问Vector中的任意元素或从末尾添加元素都可以在常量级时间复杂度内完成，而查找特定值的元素所处的位置或是在Vector中插入元素则是线性时间复杂度。