做期货新闻比较好的网站,合肥网站推广公司,企业网站建设平台的分析,安徽房产网站建设STL中优先级队列本质上就是堆。在上一篇博客中讲到过#xff1a;堆是一种完全二叉树#xff0c;逻辑结构上看起来像树#xff0c;但在物理结构中是存储在线性表中。与普通线性表不同的是#xff0c;堆中数据大小是规律排列的#xff1a;小堆中每个节点都大于它的父节点堆是一种完全二叉树逻辑结构上看起来像树但在物理结构中是存储在线性表中。与普通线性表不同的是堆中数据大小是规律排列的小堆中每个节点都大于它的父节点大堆中每个节点都小于它的父节点。此时就造成小堆中的根节点一定是所有数据中最小的而大堆中的根节点一定是所有数据中最大的。 #includeiostream
using namespace std;
namespace yhy{#includevector#includefunctionaltemplateclass Tclass less{bool operator()(const T front, const T back){return front back;}};templateclass Tclass greater{bool operator()(const T front, const T back){return front back;}};template class T, class Container vectorT, class Compare lessT class priority_queue{public:priority_queue(){}template class InputIteratorpriority_queue(InputIterator first, InputIterator last):c(first,last){for (size_t i 1; i c.size() - 1;i){adjust_up(i);}}bool empty() const{return c.empty();}size_t size() const{return c.size();}T top() const{return c[0];}void adjust_up(size_t i){while (i 0){if (comp(c[(i-1)/2], c[i])){swap(c[i], c[(i - 1) / 2]);i (i - 1) / 2;}elsebreak;}}void adjust_down(size_t i){size_t j size();size_t child i * 2 1;while (j i){if (comp(c[child], c[child 1]) child j){child;}if (comp(c[i], c[child])){swap(c[i], c[(child]);i i * 2 1;}elsebreak;}}void push(const T x){c.push_back(x);adjust_up();}void pop(){swap(c[0], c[c.size() - 1]);adjust_down();}private:Container c;Compare comp;};};
