#pragma once
创新互联一直在为企业提供服务，多年的磨炼，使我们在创意设计，
成都全网营销到技术研发拥有了开发经验。我们擅长倾听企业需求，挖掘用户对产品需求服务价值，为企业制作有用的创意设计体验。核心团队拥有超过10年以上行业经验，涵盖创意，策化，开发等专业领域，公司涉及领域有基础互联网服务
成都天府联通服务器托管、
重庆APP软件开发、手机移动建站、网页设计、网络整合营销。
#include
#include
#include
#include
using namespace std;
//仿函数实现在建堆时确定（大小堆）
template
struct Greater
{
bool operator()(const T& left,const T& right)
{
return left > right;
}
};
template
struct Less
{
bool operator()(const T& left, const T& right)
{
return left < right;
}
};
template>//默认建小堆
class Heap
{
public:
Heap()
{
}
Heap(const T* array, size_t size)
{
assert(array);
for (size_t i = 0; i < size; ++i)
{
_vec.push_back(array[i]);
}
for (int i = _vec.size() / 2 - 1; i >= 0; --i)
{
_AdjustDown(_vec, i, _vec.size());
}
}
Heap(const vector& vec)
{
_vec.swap(vec);
for (int i = _vec.size() / 2 - 1; i >= 0; --i)
{
_AdjustDown(_vec, i, _vec.size());
}
}
void Push(const T& x)
{
_vec.push_back(x);
if (_vec.size() > 0)
_AdjustUp(_vec, _vec.size() - 1);
}
void Pop()
{
swap(_vec[0], _vec[_vec.size() - 1]);
_vec.pop_back();
_AdjustDown(_vec, 0, _vec.size());
}
const T& GetTop()
{
assert(_vec.size() > 0);
return _vec[0];
}
bool Empty()
{
return _vec.empty();
}
size_t Size()
{
return _vec.size();
}
private:
void _AdjustDown(vector& vec,int root,int size)
{
int left = root * 2 + 1;
while (left < size)
{
if (left+1 < size && Compare()(vec[left+1], vec[left]))
++left;
if (Compare()(vec[left], vec[root]))
{
swap(vec[left], vec[root]);
root = left;
left = root * 2 + 1;
}
else
break;
}
}
void _AdjustUp(vector& vec,int index)
{
int parent = index >> 1;
while (Compare()(vec[index], vec[parent]))
{
swap(vec[index], vec[parent]);
index = parent;
parent = index >> 1;
}
}
protected:
vector _vec;//底层使用vector来实现
};
void test()
{
int arr[] = { 1, 2, 8, 9, 7, 4, 6, 5, 11, 10 };
Heap h(arr, sizeof(arr) / sizeof(arr[0]));
h.Push(0);
h.Pop();
cout << h.GetTop() << endl;
h.Pop();
}
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
本文标题：数据结构C++实现基本的堆-创新互联
网页路径：
http://cdkjz.cn/article/dpgego.html
