Loading... 前几天翻了一下之前的代码，感觉模板类看着好难受(并且写的不是很好)，所以重写了一遍。 ```cpp #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; } ``` 树状输出实在懒得写了，想写可以自己写吧。 最后修改：2019 年 04 月 08 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏