网站设计与开发培训,网站开发源代码知识产权归属,怎样注册代理记账公司,如何推广自己的网站文章目录 大根堆 大根堆 这一篇中我会给出一个基于C模板实现的比较完善的heap类#xff0c;你只需要简单地修改就可以把它变为小根堆
#include iostream
#include vector
#include cmath
using namespace std;templatetypename T
class heap… 文章目录 大根堆 大根堆 这一篇中我会给出一个基于C模板实现的比较完善的heap类你只需要简单地修改就可以把它变为小根堆
#include iostream
#include vector
#include cmath
using namespace std;templatetypename T
class heap
{// Big root heap
public:vectorT data;size_t size;heap(){size 0;}heap(vectorT nums){// 99 5 36 7 22 17 46 12 2 19 25 28 1 92this-data nums;this-size nums.size() - 1;for (size_t i size / 2; i 1; i--) {siftdown(i);}}void siftup(size_t i){bool check false;if (i 1) return;else {while (i ! 1 !check) {if (this-data[i] this-data[i / 2]) {T temp this-data[i / 2];this-data[i / 2] this-data[i];this-data[i] temp;i / 2;}else check true;}}return;}void siftdown(size_t i){bool check false;size_t t 0;while (i * 2 this-size !check) {if (this-data[i] this-data[i * 2]) {t i * 2;}else t i;if (i * 2 1 this-size) {if (this-data[t] this-data[i * 2 1]) {t i * 2 1;}}if (t ! i) {T temp this-data[t];this-data[t] this-data[i];this-data[i] temp;i t;}else {check true;}}return;}T deletemin(){T temp this-data[1];this-data[1] this-data[this-size--];siftdown(1);return temp;}void addElement(T num){this-data.push_back(num);this-size;siftup(this-size);}void heap_sort(){heapT h_temp{ *this };while (h_temp.size 1) {cout h_temp.deletemin() ;}cout endl;}void heap_select(int m){if (m this-size-1) heap_sort();else {int cnt{ 0 };heapT h_temp{ *this };while (cnt m) {printf(%d , h_temp.deletemin());cnt;}printf(\n);}}bool empty(){if (this-size 0) return true;else return false;}templatetypename Ufriend ostream operator(ostream output, heapU h){size_t n 1;for (size_t i 1; i h.size; i) {output h.data[i] ;if (i n * 2 - 1) {output endl;n * 2;}}output endl;return output;}
};这里没有给出对应的测试代码你可以自己写一个main函数来测试一下我的测试中它并没有出什么问题
