前几天翻了一下之前的代码,感觉模板类看着好难受(并且写的不是很好),所以重写了一遍。
#include <iostream>
#include <vector>
#include <queue>
#include <ctime>
#include <cmath>
using namespace std;
class heap
{
private:
/*存放数据*/
vector<int> value;
/*调整节点位置*/
void siftdown(int i);
void siftup(int i);
void adjust();
public:
/*构造 && 析构*/
heap() { value.resize(1); }//编号为0的空间是不用的
~heap() { }
/*创建 && 插入*/
void create(int a[], const int &n);
void create(const vector<int> &n);
void insert(const int &v);
/*删除 && 清空*/
void clear() { value.clear(); }
int pop_front();
bool erase(const int &pos);
/*堆信息*/
bool empty() { return value.empty(); }
int size() { return value.size() - 1; }
int top_value() { return value[1]; }
/*查找*/
int find(const int &v);
/*排序*/
void sort(int res[]);
void sort(vector<int> &res);
/*其它*/
void travel();
};
/*****************************************************************
Function:siftdown
Description:将一个节点向下调整。
*****************************************************************/
inline void heap::siftdown(int i)
{//传入一个需要调整的节点
int n = value.size();
int min_pos = i;//min_pos用来判断是否需要继续循环
bool flag = true;//flag用来记录是否继续循环
while (i * 2 < n && flag)
{//在第i个节点有左儿子且需要继续调整的时候循环。
min_pos = value[i * 2] < value[i] ? i * 2 : i;
//判断父亲和左儿子的关系
if (i * 2 + 1 < n)//判断右儿子(如果有的话)
if (value[i * 2 + 1] < value[i])
min_pos = i * 2 + 1;
if (min_pos == i)//不需要改变了
flag = false;
else //有比父节点还小的子节点,交换
{
int tmp = value[min_pos];
value[min_pos] = value[i];
value[i] = tmp;
i = min_pos;//更新 i,方便继续调整
}
}
return;
}
/*****************************************************************
Function:siftup
Description:将一个节点向上调整。
*****************************************************************/
inline void heap::siftup(int i)
{
bool flag = true; //是否需要调整的标志
while (flag)
{
if (i == 1)//如果达到堆顶了
return;
if (value[i] < value[i / 2])
{ //如果子节点比父节点小,交换
int tmp = value[i];
value[i] = value[i / 2];
value[i / 2] = tmp;
}
else
flag = false;
i /= 2;//方便后面调整
}
return;
}
/*****************************************************************
Function:adjust
Description:将数组调整成堆。
*****************************************************************/
inline void heap::adjust()
{
for (int i = value.size() / 2; i > 0; i--)
siftdown(i);//从最后一个非叶节点开始调整
return;
}
/*****************************************************************
Function:create
Description:创建一个堆。
*****************************************************************/
inline void heap::create(int a[], const int & n)
{
for (int i = 0; i < n; i++)
value.push_back(a[i]);
adjust();//插入后调整位置
}
inline void heap::create(const vector<int>& n)
{
value = n;
adjust();
return;
}
/*****************************************************************
Function:insert
Description:将一个节点插入到堆里。
*****************************************************************/
inline void heap::insert(const int & v)
{
value.push_back(v);//将数据插入
siftup(value.size() - 1);//再调整位置
return;
}
/*****************************************************************
Function:pop_front
Description:删除堆顶。
*****************************************************************/
inline int heap::pop_front()
{
int tmp = value[1];
erase(1);
return tmp;
}
/*****************************************************************
Function:erase
Description:将一个节点删除。
*****************************************************************/
inline bool heap::erase(const int & pos)
{
if (pos > 0 && pos < value.size())
{//在范围内才执行删除
value[pos] = value[value.size() - 1];
value.pop_back();
siftdown(pos);
return true;
}
return false;
}
/*****************************************************************
Function:find
Description:查找一个节点,返回其位置。
*****************************************************************/
inline int heap::find(const int & v)
{//利用广搜思想来查找
if (empty())//判空
return 0;
queue<int> q;
q.push(1);
while (!q.empty())
{//运用队列遍历堆
int tmp = q.front();
q.pop();
if (value[tmp] == v)
return tmp;//找到就返回位置
if (value[tmp] > v)//最小值都比要查找的值大
continue;//下面也没必要执行了
/*判断左右儿子是否存在,存在就加入队列*/
if (tmp * 2 < value.size())
q.push(tmp * 2);
if (tmp * 2 + 1 < value.size())
q.push(tmp * 2 + 1);
}
return 0;
}
/*****************************************************************
Function:sort
Description:堆排序。
*****************************************************************/
inline void heap::sort(int res[])
{
heap tmp = *this;
int cnt = 0;
clock_t begin, end;
begin = clock();
while (!tmp.empty())
res[cnt++] = tmp.pop_front();
end = clock();
cout << "Used time = " << (double)(end - begin) / CLOCKS_PER_SEC << " s" << endl;
return;
}
inline void heap::sort(vector<int>& res)
{
res.clear();
heap tmp = *this;
int cnt = 0;
clock_t begin, end;
begin = clock();
while (!tmp.empty())
res.push_back(tmp.pop_front());
end = clock();
cout << "Used time = " << (double)(end - begin) / CLOCKS_PER_SEC << " s" << endl;
return;
}
/*****************************************************************
Function:travel
Description:输出堆。
*****************************************************************/
inline void heap::travel()
{
cout << "The elements in this heap is :" << endl;
for (int i = 1; i < value.size(); i++)
cout << value[i] << " ";
cout << endl;
return;
}
树状输出实在懒得写了,想写可以自己写吧。