Loading... 今天原本是学习堆排序的，学了这个最小堆就顺手补充了一点。在这里记录一下我写的最小堆吧。 ##1.堆的性质 （1）堆中某个节点的值总是不大于或不小于其父节点的值； （2）堆总是一棵完全二叉树。 ##2.代码实现 ```cpp #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.测试代码 我把测试用的代码也记录一下吧 ```cpp #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。只不过这个是最大堆。 最后修改：2019 年 04 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏