#pragma once
#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.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
{
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
{
int parent = index >> 1;
while (Compare()(vec[index], vec[parent]))
{
swap(vec[index], vec[parent]);
index = parent;
parent = index >> 1;
}
}
protected:
vector
};
void test()
{
int arr[] = { 1, 2, 8, 9, 7, 4, 6, 5, 11, 10 };
Heap
h.Push(0);
h.Pop();
cout << h.GetTop() << endl;
h.Pop();
}
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
