#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)
{
_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();
}
文章标题：数据结构C++实现基本的堆
本文网址：
http://cdkjz.cn/article/gihsco.html
