今天原本是学习堆排序的，学了这个最小堆就顺手补充了一点。在这里记录一下我写的最小堆吧。
1.堆的性质
（1）堆中某个节点的值总是不大于或不小于其父节点的值；
（2）堆总是一棵完全二叉树。
2.代码实现
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <Windows.h>//这个是测试用的头文件
using namespace std;
template<typename T>class heap
{
private:
vector<T> value;//使用vector方便扩展
public:
heap();
~heap();
void siftdown(int i);
void siftup(int i);
void creat();
void creat(T a[], const int &n);
void creat(const vector<T> &n);
void insert(const T &v);
void clear();
bool empty();
int size();
int find(const T &v);
T pop_front();
bool erase(const T &v);
void sort(T res[]);
void sort(vector<T> &res);
void print();
};
//#include "Function.cpp"
//#include "tree.cpp"
const double EPS = 1E-6;
template<typename T>heap<T>::heap()
{ //构造函数
value.resize(1);
}
template<typename T>heap<T>::~heap()
{ }//析构函数
template<typename T> void heap<T>::siftdown(int i)
{ //传入一个需要向下调整的节点的编号i
int n = value.size() - 1;
int min_pos;//min_pos记录最小的值的位置
bool flag = true;//flag用于标记是否需要继续循环
while (i * 2 <= n && flag)
{//当父节点有子节点（最少是左儿子）且需要调整时循环
if (value[i * 2] < value[i])//判断左儿子
min_pos = i * 2;
else
min_pos = i;
if (i * 2 + 1 <= n)//判断右儿子（如果有的话）
if (value[i * 2 + 1] < value[min_pos])
min_pos = i * 2 + 1;
if (i == min_pos)//已经不需要改变了
flag = false;
else//如果有比父节点小的子节点，则交换它们
{
T temp = value[i];
value[i] = value[min_pos];
value[min_pos] = temp;
i = min_pos;//将i更新，以便接下来的调整
}
}
return;
}
template<typename T>void heap<T>::siftup(int i)
{
bool flag = true;//是否需要继续调整的标志
while (flag)
{
if (i == 1)//如果是堆顶则无需调整
return;
if (value[i] < value[i / 2])
{//判断它与父节点的关系。如果比父亲小则交换
T temp = value[i];
value[i] = value[i / 2];
value[i / 2] = temp;
}
else
flag = false;
i /= 2;//为了后面的调整做准备
}
return;
}
template<typename T> void heap<T>::creat()
{
for (int i = value.size() / 2; i > 0; i--)
siftdown(i);//从最后一个非叶节点开始调整
return;
}
template<typename T> void heap<T>::creat(T a[],const int &n)
{
for (int i = 0; i < n; i++)
value.push_back(a[i]);
this->creat();
return;
}
template<typename T> void heap<T>::creat(const vector<T> &v)
{
value = v;
this->creat();
return;
}
template<typename T> void heap<T>::insert(const T &v)
{
value.push_back(v);
siftup(value.size() - 1);
return;
}
template<typename T> void heap<T>::clear()
{
value.clear();
value.resize(1);
return;
}
template<typename T> bool heap<T>::empty()
{
return value.size() == 1;
}
template<typename T> int heap<T>::size()
{
return value.size() - 1;
}
template<typename T> int heap<T>::find(const T &v)
{//这里的find用了广搜的思想
if (this->empty())
return -1;//判空
queue<int> q;
q.push(1);
while (!q.empty())//运用队列来遍历这棵树
{
int temp = q.front();
q.pop();
if (v == value[temp])
return temp;
if (value[temp] > v)
continue;
else
{
if (2 * temp < value.size())
q.push(2 * temp);
if (2 * temp + 1 < value.size())
q.push(2 * temp + 1);
}
}
return 0;
}
template<typename T> T heap<T>::pop_front()
{
T temp = value[1];//用临时变量记录堆顶的值
value[1] = value[value.size() - 1];//将堆的最后一个值赋值给堆顶
value.pop_back();//删除最后一个元素
siftdown(1);//调整堆
return temp;
}
template<typename T> bool heap<T>::erase(const T &pos)
{
if (pos > 0 && pos < value.size())
{
value[pos] = value[value.size() - 1];
value.pop_back();
siftdown(pos);
return true;
}
return false;
}
template<typename T> void heap<T>::sort(T res[])
{//实现堆排序
heap<T> temp = *this;
int cnt = 0;
clock_t begin, end;
begin = clock();
while (!temp.empty())
res[cnt++] = temp.pop_front();
end = clock();
cout << "Used time = " << (double)(end - begin)/CLOCKS_PER_SEC << " s" << endl;
return;
}
template<typename T> void heap<T>::sort(vector<T> &res)
{
res.clear();
heap<T> temp = *this;
int cnt = 0;
clock_t begin, end;
begin = clock();
while (!temp.empty())
res.push_back(temp.pop_front());
end = clock();
cout << "Used time = " << (double)(end - begin) / CLOCKS_PER_SEC << " s" << endl;
return;
}
template<typename T> void heap<T>::print()
{
cout << "The elements in this heap is :" << endl;
for (int i = 1; i < value.size(); i++)
cout << value[i] << " ";
cout << endl;
return;
}上面就是我写的最小堆的代码。
3.测试代码
我把测试用的代码也记录一下吧
#include "heap.cpp"//我是用VS分成两个板块写的，所以会有这个头文件。
int main()
{
int n;
heap<int> h;
vector<int> arr;
while (true)
{
cout << "此时堆里面有" << h.size() << "个数" << endl;
char command;
cout << "请输入指令（数字）" << endl;
cout << "指令列表：\n1.Input：输入\n2.Find：查找\n3.Clear：删除堆\n4.Erase：删除元素\n5.Pop：删除最小元素\n6.Element：输出堆里的元素\n7.Sort：排序\n0.Exit：退出" << endl;
cin >> command;
switch (command)
{
case '1':
{
int n;
cout << "你想输入几个数？" << endl;
cin >> n;
cout << "那就输入" << n << "个数吧" << endl;
for (int i = 0; i < n; i++)
{
int temp;
cin >> temp;
h.insert(temp);
}
cout << "输入完成！" << endl;
break;
}
case '2':
{
int v;
cout << "你要查找哪个数？" << endl;
cin >> v;
int pos = h.find(v);
pos ? cout << v << "是第" << pos << "个数" << endl : cout << "未找到" << v << endl;
break;
}
case '3':
{
h.clear();
cout << "堆已清空！" << endl;
break;
}
case '4':
{
int v;
cout << "你想删除哪个数" << endl;
cin >> v;
h.erase(h.find(v)) ? cout << "删除成功！" << endl : cout << "没有这个数哦" << endl;
break;
}
case '5':
{
int temp = h.pop_front();
cout << "删除成功！删除的数为" << temp << endl;
break;
}
case '6':
cout << "堆里面的元素有：" << endl;
h.print();
break;
case '7':
h.sort(arr);
cout << "排序结果是：" << endl;
for (int i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << endl;
break;
case '0':
cout << "程序将于2秒后退出" << endl;
goto END;
default:
cout << "请输入正确的指令！" << endl;
break;
}
system("pause");
system("cls");
}
END:Sleep(2000);
return 0;
}这只是我模仿写的一个最小堆，有什么错误请指正。
最后，堆其实就是优先队列，在STL库中也有相应的模板：priority_queue。只不过这个是最大堆。
