堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。
创新互联从2013年开始，先为雁江等服务建站，雁江等地企业，进行企业商务咨询服务。为雁江企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
堆结构的二叉树存储是
这是一个普通的堆，我们想把它变成大堆，就必须了解大堆的特点。然后我们对它进行调整，保证每个父节点的都大于孩子节点。
我们先调整这个二叉树的一部分，从它的最后一个节点开始调整，图中红色箭头开始调整，如果父节点小于孩子节点，就交换，否则结束。在看下一个节点，一直这样循环，直到全部调整完。
代码如下：
void _AdjustDown(size_t parent, size_t size)
{
size_t child = 2 * parent + 1;
while (child < size)
{
//child + 1 < size保证是最后一个节点
if (child + 1 < size&&_arr[child] < _arr[child + 1])
{
child++;//孩子节点大的一个节点
}
//交换
if (_arr[child]>_arr[parent])
{
swap(_arr[child],_arr[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}如果想把它调整成最小堆，必须符合每个父节点的都小于孩子节点，代码原理和大堆相似。
代码如下：
void _AdjustUp(int child)
{
int parent = (child - 1) / 2;
int size = _arr.size();
while (child > 0)
{
if (_arr[child] > _arr[parent])
{
swap(_arr[child], _arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}下面我给出完整代码，构造函数用的是调整成大堆。为了让代码更简洁，实现过程借用了库函数中的vector。
代码如下：
Heap.h中
#include
#include
template
class Heap
{
public:
Heap()
:_arr(NULL)
{}
//构造函数
Heap(const T*arr, size_t size)
{
_arr.reserve(size);
for (size_t i = 0; i < size; i++)
{
_arr.push_back(arr[i]);
}
for (int j = (_arr.size() - 2) / 2; j >= 0; j--)
{
_AdjustDown(j, size);
}
}
//拷贝构造
Heap(const vector& h)
{
_arr.reserve(_arr.size());
for (size_t i = 0; i < _arr.size(); i++)
{
_arr.push_back(h[i]);
}
}
//先储存在顺序表中，在进行下调
void push(const T& x)
{
_arr.push_back(x);
_AdjustUp(_arr.size()-1);
}
//删除
void pop()
{
size_t size = _arr.size();
assert(size > 0);
swap(_arr[0], _arr[size - 1]);//先把根结点和要删除的结点交换
_arr.pop_back();//然后删除
size = _arr.size();
_AdjustDown(0, size);//最后上调
}
//堆是否为空
bool Empty()
{
size_t size = _arr.size();
assert(size >= 0);
return size == 0;
}
//堆的大小
size_t Size()
{
size_t size = _arr.size();
assert(size >= 0);
return size;
}
//访问根结点
T& Top()
{
size_t size = _arr.size();
assert(size > 0);
return _arr[0];
}
void Print()
{
for (int i = 0; i < Size(); i++)
{
cout << _arr[i] << " ";
}
cout << endl;
}
protected:
//下调
void _AdjustDown(size_t parent, size_t size)
{
size_t child = 2 * parent + 1;
while (child < size)
{
//child + 1 < size保证是最后一个节点
if (child + 1 < size&&_arr[child] < _arr[child + 1])
{
child++;//孩子节点大的一个节点
}
//交换
if (_arr[child]>_arr[parent])
{
swap(_arr[child],_arr[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
//上调
void _AdjustUp(int child)
{
int parent = (child - 1) / 2;
int size = _arr.size();
while (child > 0)
{
if (_arr[child] > _arr[parent])
{
swap(_arr[child], _arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
protected:
vector _arr;
};
test.cpp中
#include
using namespace std;
#include"Heap.h"
void Test()
{
int a[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
Heap h(a, sizeof(a) / sizeof(a[0]));
h.Print();
h.push(20);
h.Print();
h.pop();
h.Print();
Heap h2(h);
h2.Print();
}
int main()
{
Test();
system("pause");
return 0;
}
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
标题名称：用模板实现堆-创新互联
网站网址：
http://bjjierui.cn/article/cdiehp.html
