【数据结构】用模版实现大小堆、实现优先级队列,以及堆排序
一、用模版实现大小堆
创新互联是一家专注于网站设计制作、网站设计与策划设计,镜湖网站建设哪家好?创新互联做网站,专注于网站建设十余年,网设计领域的专业建站公司;建站业务涵盖:镜湖等地区。镜湖做网站价格咨询:18980820575
如果不用模版的话,写大小堆,就需要分别实现两次,但是应用模版的话问题就简单多了,我们只需要实现两个仿函数,Greater和Less就行了,仿函数就是用类实现一个()的重载就实现了仿函数。这个看下代码就能理解了。再设计参数的时候,需要把模版设计成模版的模版参数,因为要实现大小堆嘛!当我们实现好一个大堆或者小队的逻辑后只需要用模版接收的Greater或Less类定义一个变量,就能实现通用功能了。
templatestruct Less { bool operator()(const T& l, const T& r) { return l < r; } }; template struct Greater { bool operator()(const T& l, const T& r) { return l>r; } }; template class compare = less> class Heap { public: Heap() {} Heap(T* a,size_t size) { size_t index = 0; while (index < size) { _a.push_back(a[index]); index++; } for (int i = (_a.size() - 2) / 2; i >= 0; i--) _AdjustDown(i); } void push(const T& x) { _a.push_back(x); _AdjustUp(_a.size() -1); } void pop() { size_t size = _a.size(); assert(size > 0); swap(_a[0], _a[size - 1]); _a.pop_back(); size = _a.size(); _AdjustDown(0); } size_t top() { assert(!_a.empty()); return _a[0]; } bool empty() { return _a.size() == 0; } size_t Size() { return _a.size(); } void Print() { for (int i = 0; i < _a.size(); i++) { cout << _a[i] << " "; } cout << endl; } protected: void _AdjustUp(int child) { int parent = (child - 1) / 2; compare com; //如果是大堆传过来就是用大堆的逻辑,小堆就实现小堆的逻辑 while (child > 0) { //找出孩子中的最大孩子 if (com(_a[child] , _a[parent])) { swap(_a[child], _a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void _AdjustDown(size_t parent) { size_t child = 2 * parent + 1; compare com; //如果是大堆传过来就是用大堆的逻辑,小堆就实现小堆的逻辑 while (child < _a.size()) { //找出孩子中的最大孩子 if (child + 1 < _a.size() && com(_a[child+1] ,_a[child])) { ++child; } //把 if (com(_a[child] , _a[parent])) { swap(_a[parent], _a[child]); parent = child; child = child * 2 + 1; } else { break; } } } protected: vector _a; };
二、用模版实现优先级队列
前面实现了大小堆,这里我们可以使用适配器,直接调用大小堆,来实现优先级队列。
templateclass compare = Less> class priorityQueue { private: Heap _hp; public: void push(const T& x) { _hp.push(x); } void pop() { _hp.pop(); } T& Top() { return _hp.top(); } void Print() { _hp.Print(); } };
三、堆排序的实现
堆排序的实现简单思路,(升序)先构造出来一个大堆,调整堆后,将堆头和最后一个数据交换,最大值就换到了数组的最后,然后在调整堆,但是size需要减少1,因为最大的已经调整到最后,如果再加上它调整又会回到堆头。
int*& HeapSort(int* a, size_t size) { for (int i = (size - 2) / 2; i >= 0; i--) { _AdjustDown(a, size, i); } for (int i = 0; i < size; i++) { swap(a[0], a[size - i - 1]); _AdjustDown(a, size - i - 1, 0); } return a; }
当前标题:【数据结构】用模版实现大小堆、实现优先级队列,以及堆排序
网站地址:http://pwwzsj.com/article/jeiogo.html