【数据结构】堆的实现（包括：默认成员函数，插元素push,删元素p

在数据结构里，堆是一类很重要的结构。堆结构是一组数组对象，我们可以把它当作是一颗完全二叉树。

最大堆：堆里每一个父亲节点大于它的子女节点。

最小堆：堆里每一个父亲节点小于它的子女节点。

如图就是一个最大堆:

实现代码时我的测试序列是：int a[] = { 10,11,13,12,16,18,15,17,14,19 };

我们把它的图画出来，便于分析。

实现代码如下：

建立头文件heap.hpp

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

建立源文件heap.cpp

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

关于size(),GetTop()等函数我们可以通过测试函数Test()写出适当的测试用例来测试，而堆h1,h2是否转变成大根堆的实现，我们可以通过调试来查看，如图：

（编辑：李大同）

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