#include <iostream> using namespace std; #include <vector> #include <assert.h> //仿函数 template<class T> struct Less { bool operator()(const T& left, const T& right) { return left < right; } }; template<class T> struct Greater { bool operator()(const T& left, const T& right) { return left > right; } }; template<class T, class Compare = Less<T>>//默认为小堆 class Heap { public: Heap() {} Heap(const T* array, size_t size) { for (size_t i = 0; i < size; ++i) { _a.push_back(array[i]); } 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() { assert(!_a.empty()); swap(_a[0], _a[_a.size()-1]); _a.pop_back(); _AdjustDown(0); } T& GetTop() { assert(!_a.empty()); return _a[0]; } bool Empty() { return _a.empty(); } size_t Size() { return _a.size(); } void Print() { for (size_t i = 0; i < _a.size(); ++i) { cout<<_a[i]<<" "; } cout<<endl; } protected: //向下调整 void _AdjustDown(size_t parent) { Compare compare; size_t child = parent*2 + 1; while (child < _a.size()) { //比较左右孩子 if (child+1 < _a.size() && compare(_a[child+1], _a[child])) { ++child; } if (compare(_a[child], _a[parent])) { swap(_a[child], _a[parent]); parent = child; child = parent*2 + 1; } else { break; } } } //向上调整 void _AdjustUp(size_t child) { Compare compare; size_t parent = (child-1)/2; while (child > 0) { if (compare(_a[child], _a[parent])) { swap(_a[parent], _a[child]); child = parent; parent = (child-1)/2; } else { break; } } } protected: vector<T> _a; }; void Test() { int a[10] = {10, 11, 13, 12, 16, 18, 15, 17, 14, 19}; Heap<int, Greater<int>> hp1(a, sizeof(a)/sizeof(a[0])); hp1.Print(); cout<<"size:"<<hp1.Size()<<endl; cout<<"top:"<<hp1.GetTop()<<endl; cout<<"empty:"<<hp1.Empty()<<endl; } int main() { Test(); return 0; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。