1. 普通版本实现优先级队列
1.1 push()
void adjust_up(int child) { int parent = (child - 1) / 2; while (child > 0) { if (_container[parent] < _container[child]) { swap(_container[parent], _container[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void push(const T& val) { _container.push_back(val); adjust_up(_container.size() - 1); }
1.2 pop()
void adjust_down(int parent) { int child = parent * 2 + 1; while (child < _container.size()) { if (child + 1 < _container.size() && _container[child] < _container[child + 1]) { child = child + 1; } if (_container[parent] < _container[child]) { swap(_container[parent], _container[child]); parent = child; child = parent * 2 + 1; } else { break; } } } void pop() { swap(_container[0], _container[_container.size() - 1]); _container.pop_back(); adjust_down(0); }
1.3 top()
const T& top() { return _container[0]; }
1.4 size()
size_t size() { return _container.size(); }
1.5 empty()
bool empty() { return _container.empty(); }
1.6 完整代码
namespace my_priority_queue { template <class T, class Container = vector<int>> class priority_queue { public: void adjust_up(int child) { int parent = (child - 1) / 2; while (child > 0) { if (_container[parent] < _container[child]) { swap(_container[parent], _container[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(int parent) { int child = parent * 2 + 1; while (child < _container.size()) { if (child + 1 < _container.size() && _container[child] < _container[child + 1]) { child = child + 1; } if (_container[parent] < _container[child]) { swap(_container[parent], _container[child]); parent = child; child = parent * 2 + 1; } else { break; } } } void push(const T& val) { _container.push_back(val); adjust_up(_container.size() - 1); } void pop() { swap(_container[0], _container[_container.size() - 1]); _container.pop_back(); adjust_down(0); } const T& top() { return _container[0]; } size_t size() { return _container.size(); } bool empty() { return _container.empty(); } private: Container _container; }; }
2. 仿函数实现优先级队列
namespace my_priority_queue { template <class T> struct less { bool operator()(const T& x, const T& y) { return x < y; } }; template <class T> struct greator { bool operator()(const T& x, const T& y) { return x > y; } }; template <class T, class Container = vector<int>, class Compare = less<int>> class priority_queue { public: void adjust_up(int child) { Compare compare; int parent = (child - 1) / 2; while (child > 0) { //if (_container[parent] < _container[child]) if (compare(_container[parent],_container[child])) { swap(_container[parent], _container[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(int parent) { Compare compare; int child = parent * 2 + 1; while (child < _container.size()) { if (child + 1 < _container.size() && compare(_container[child],_container[child + 1])) { child = child + 1; } if (compare(_container[parent], _container[child])) { swap(_container[parent], _container[child]); parent = child; child = parent * 2 + 1; } else { break; } } } void push(const T& val) { _container.push_back(val); adjust_up(_container.size() - 1); } void pop() { swap(_container[0], _container[_container.size() - 1]); _container.pop_back(); adjust_down(0); } const T& top() { return _container[0]; } size_t size() { return _container.size(); } bool empty() { return _container.empty(); } private: Container _container; }; }
仿函数在这里就是类中实现一个()运算符重载，通过对象直接调用，比较大小返回一个真假值。
