【数据结构】堆的实现以及简单的函数

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

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

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

(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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!