首页 > 代码库 > 大/小堆:源代码
大/小堆:源代码
#pragma once #include <vector> #include <assert.h> // // 小堆 == 大堆 // 仿函数 // template<class T> struct Greater { bool operator() (const T& l, const T& r) { return l > r; } }; template<class T> struct Less { bool operator() (const T& l, const T& r) { return l < r; } }; template<class T, class Compare = Less<T>> 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<T> _array; // 函数指针 }; void Test1() { int array[10] = {10, 16, 18, 12, 11, 13, 15, 17, 14, 19}; Heap<int, Less<int> > hp1(array, 10); hp1.Push(5); hp1.Pop(); Heap<int, Greater<int> > hp2(array, 10); hp2.Push(100); hp2.Pop(); } template<class T, class Compare = Less<T>> class PriorityQueue { public: void Push(const T& x) { _queue.Push(x); } void Pop() { _queue.Pop(); } const T& Top() { return _queue.Top(); } protected: Heap<T, Compare> _queue; }; //template<class T> //bool Greater(const T& l, const T& r); // 仿函数 void Test2() { int a1 = 10, a2 = 20; Greater<int> GreaterFunc; Less<int> LessFunc; cout<<GreaterFunc(a1, a2)<<endl; cout<<LessFunc(a1, a2)<<endl; cout<<Greater<int>()(a1, a2)<<endl; cout<<Less<int>()(a1, a2)<<endl; }
以上
本文出自 “剩蛋君” 博客,转载请与作者联系!
大/小堆:源代码
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。