在数据结构里，堆是一类很重要的结构。堆结构是一组数组对象，我们可以把它当作是一颗完全二叉树。@H_502_1@
@H_502_1@
最大堆：堆里每一个父亲节点大于它的子女节点。@H_502_1@
最小堆：堆里每一个父亲节点小于它的子女节点。@H_502_1@
如图就是一个最大堆:
@H_502_1@
实现代码时我的测试序列是：int a[] = { 10,11,13,12,16,18,15,17,14,19 };@H_502_1@
我们把它的图画出来，便于分析。@H_502_1@
#define_CRT_SECURE_NO_WARNINGS1
#include<iostream>
usingnamespacestd;
#include<assert.h>
#include<vector>
template<classT>
classHeap
{
public:
Heap()
:_a(NULL)
{}
//构造堆：先把各个元素接收到，再根据堆的特点将元素调整
Heap(constT*array,size_tsize)
{
_a.reserve(size);
for(size_ti=0;i<size;i++)
{
_a.push_back(array[i]);
}
//建堆
intSize=size;
for(intj=(_a.size()-2)/2;j>=0;j--)
{
_AdjustDown(j,Size);
}
}
//拷贝构造
Heap(constvector<T>&vec)
:_a(NULL)
{
_a.reserve(vec.size());
for(size_ti=0;i<size;i++)
{
_a.push_back(vec[i]);
}
}
//插入一个元素x:先插入到顺序表中，再根据具体元素大小向上调整确定插入元素的位置
voidPush(constT&x)
{
_a.push_back(x);
_AdjustUp(_a.size()-1);
}
//删除根节点
voidPop()
{
size_tsize=_a.size();
assert(size>0);//防御式编程，确定是否可以删除元素
swap(_a[0],_a[size-1]);//若直接删除堆的根节点，则会使堆结构紊乱
_a.pop_back();//将根节点与堆的最后一个节点交换位置，此时再对元素删除，以及将其调整于合适位置
size=_a.size();
_AdjustDown(0,size);
}
//访问堆的根节点
T&GetTop()
{
size_tsize=_a.size();
assert(size>0);
return_a[0];
}
//将根节点向下调整
void_AdjustDown(size_tparent,size_tsize)
{
size_tchild=2*parent+1;
while(child<size)
{
if(child+1<size&&_a[child]<_a[child+1])
{
child++;
}
if(_a[child]>_a[parent])
{
swap(_a[child],_a[parent]);
parent=child;
child=2*parent+1;
}
else
{
break;
}
}
}
//向上调整
void_AdjustUp(intchild)
{
//无论插节点后为左子树还是右子树，都可用(child-2)/2计算出此时父节点的下标
size_tparent=(child-1)/2;
intindex=child;
size_tsize=_a.size();
while(child<size)
{
if(index%2==0&&_a[index-1]>_a[index])
{
--child;
}
if(index%2!=0&&index+1<child&&_a[index]<_a[index+1])
{
++child;
}
if(_a[child]>_a[parent])
{
swap(_a[child],_a[parent]);
child=parent;
parent=(child-1)/2;
}
else
{
break;
}
}
}
boolEmpty()
{
size_tsize=_a.size();
assert(size>=0);
returnsize==0;
}
size_tSize()
{
size_tsize=_a.size();
assert(size>=0);
returnsize;
}
private:
vector<T>_a;
};
@H_502_1@
#define_CRT_SECURE_NO_WARNINGS1
#include"heap.hpp"
voidTest()
{
inta[]={10,19};
Heap<int>h1(a,sizeof(a)/sizeof(a[0]));
Heap<int>h2(h1);
cout<<h1.GetTop()<<endl;
cout<<h1.Size()<<endl;
h1.Push(20);
cout<<h1.GetTop()<<endl;
h1.Pop();
cout<<h1.Size()<<endl;
}
intmain()
{
Test();
system("pause");
return0;
}
@H_502_1@
关于size(),GetTop()等函数我们可以通过测试函数Test()写出适当的测试用例来测试，而堆h1,h2是否转变成大根堆的实现，我们可以通过调试来查看，如图：@H_502_1@
