大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
#pragma once #include#include // // 小堆 == 大堆 // 仿函数 // template struct Greater { bool operator() (const T& l, const T& r) { return l > r; } }; template struct Less { bool operator() (const T& l, const T& r) { return l < r; } }; template > class Heap { public: Heap() {} Heap(const T* a, size_t size) { for(size_t i = 0; i < size; ++i) { _array.push_back(a[i]); } // 构建堆 for (int i = (_array.size()-2)/2; i >=0; --i) { AdjustDown(i); } } void Push(const T& x) { _array.push_back(x); AdjustUp(_array.size() - 1); } void Pop() { assert(_array.size() > 0); swap(_array[0], _array[_array.size() - 1]); _array.pop_back(); AdjustDown(0); } void AdjustDown(int parent) { int child = parent*2+1; while(child < _array.size()) { // 找左右里面小的那一个 //if (child+1<_array.size() // && _array[child+1] > _array[child]) if (child+1 < _array.size() && Compare()(_array[child+1], _array[child])) { ++child; } // 小的孩子节点跟父节点比较 //if (_array[child] > _array[parent]) if(Compare()(_array[child], _array[parent])) { swap(_array[child], _array[parent]); parent = child; child = 2*parent+1; } else { break; } } } void AdjustUp(int child) { int parent = (child - 1)/2; //while (parent >= 0) //?parent不会小于0 while(child > 0) { //if (_array[child] > _array[parent]) if(Compare()(_array[child], _array[parent])) { swap(_array[child], _array[parent]); child = parent; parent = (child - 1)/2; } else { break; } } } int Size() { return _array.size(); } bool Empty() { return _array.empty(); } const T& Top() { return _array[0]; } protected: vector _array; // 函数指针 }; void Test1() { int array[10] = {10, 16, 18, 12, 11, 13, 15, 17, 14, 19}; Heap > hp1(array, 10); hp1.Push(5); hp1.Pop(); Heap > hp2(array, 10); hp2.Push(100); hp2.Pop(); } template > class PriorityQueue { public: void Push(const T& x) { _queue.Push(x); } void Pop() { _queue.Pop(); } const T& Top() { return _queue.Top(); } protected: Heap _queue; }; //template //bool Greater(const T& l, const T& r); // 仿函数 void Test2() { int a1 = 10, a2 = 20; Greater GreaterFunc; Less LessFunc; cout< ()(a1, a2)< ()(a1, a2)< 以上
10年专注成都网站制作,成都定制网页设计,个人网站制作服务,为大家分享网站制作知识、方案,网站设计流程、步骤,成功服务上千家企业。为您提供网站建设,网站制作,网页设计及定制高端网站建设服务,专注于成都定制网页设计,高端网页制作,对凿毛机等多个方面,拥有多年的营销推广经验。
当前标题:大/小堆:源代码
标题链接:http://dzwzjz.com/article/jccccs.html