堆是什么?刚接触到这个概念估计都摸不着头脑,不知道堆是什么样个东西。简单介绍下,

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

堆结构的二叉树存储有两种情况:

(1).最大堆:每个父节点的都大于孩子节点。

(2).最小堆:每个父节点的都小于孩子节点。


举个例子可能好理解些,看下面:

int a[] = {10,11,13,12,16,18,15,17,14,19};


熟悉了它的结构,给解释下怎么来构建这个堆。

对于他的实现,我们直接可以借用vector作为成员,因为使用到的数组要实现增删查改,增容是肯定会用到的,将传过来的数组全部push_back到vector中去,然后从最后一个非叶子节点开始向下调整,知道最后调整玩根结点,就完成了堆的构成。


那么什么叫做向下调整了?

向下调整就是从第一个非叶子节点作为一颗子树开始调整,将大的数据放大父节点上,依次调整,直至调整到根节点为止

#include<vector>template<classT>classHeap{public:Heap(){}Heap(T*a,size_tsize){size_tindex=0;while(index<size){_a.push_back(a[index]);index++;}for(inti=(_a.size()-2)/2;i>=0;i--)_AdjustDown(i);}void_AdjustDown(size_tparent){size_tchild=2*parent+1;while(child<_a.size()){//找出孩子中的最大孩子if(child+1<_a.size()&&_a[child]<_a[child+1]){++child;}//把if(_a[parent]<_a[child]){swap(_a[parent],_a[child]);parent=child;child=child*2+1;}else{break;}}


下面再重点介绍下pop函数的写法,pop函数就相当于将根节点删除了,我们转换下思路,将根节点和最后一个节点交换,然后就需要写一个向上调整的函数就行了。向上调整的思路:由于交换后根节点变成了最后一个节点的值,比原来根节点的左右小,所以需要用左右节点中的大值将这个小值换下来。


voidpop(){size_tsize=_a.size();assert(size>0);swap(_a[0],_a[size-1]);_a.pop_back();size=_a.size();_AdjustDown(0);}void_AdjustUp(intchild){intparent=(child-1)/2;while(parent>=0){//找出孩子中的最大孩子if(_a[child]>_a[parent]){swap(_a[child],_a[parent]);child=parent;parent=(child-1)/2;}else{break;}}}


其他函数:

voidpush(constT&x){_a.push_back(x);_AdjustUp(_a.size()-1);}size_ttop(){assert(!_a.empty());return_a[0];}boolempty(){return_a.size()==0;}size_tSize(){return_a.size();}voidPrint(){for(inti=0;i<_a.size();i++){cout<<_a[i]<<"";}cout<<endl;}