东阳网站建设公司,公司网站制作开发公司,网站建设优化400报价,爱演示网目录 priority_queue的作用priority_queue的接口构造函数emptysizetoppushpopswap priority_queue的实现仿函数#xff08;函数对象#xff09;是什么#xff1f;向上调整算法#xff08;adjustup#xff09;向下调整算法#xff08;adjustdown#xff09;迭代器构造pus… 目录 priority_queue的作用priority_queue的接口构造函数emptysizetoppushpopswap priority_queue的实现仿函数函数对象是什么向上调整算法adjustup向下调整算法adjustdown迭代器构造pushpop priority_queue的作用
priority_queue翻译过来就是优先级队列是stl提供的一个容器适配器也就是我们数据结构中学到的栈是一种常用的数据结构特点是利用类似二叉树的结构让父节点元素比子节点大从而使对顶元素最大小。
priority_queue的接口
构造函数
explicit priority_queue (const Compare comp Compare(),const Container ctnr Container());
template class InputIteratorpriority_queue (InputIterator first, InputIterator last,const Compare comp Compare(),const Container ctnr Container());可以用默认构造和迭代器构造支持指定容器和仿函数对象。
empty
bool empty() const;堆的判空。
size
size_type size() const;返回堆的元素数。
top
const value_type top() const;返回堆顶元素。
push
void push (const value_type val);入堆。
pop
void pop();出对顶的元素。
swap
void swap (priority_queue x) noexcept (/*see below*/);priority_queue自己的交换函数。
priority_queue的实现
#includeiostream#includevectorusing namespace std;namespace jiunian
{templateclass T, class container vectorT, class compare lessTclass priority_queue{public:typedef priority_queueT, container Self;priority_queue(){}templateclass Iteratorpriority_queue(Iterator begin, Iterator end){Iterator cur begin;while (cur ! end) con.push_back(*(cur));int pos size() / 2 - 1;while (pos 0) adjustdown(pos--);}bool empty() const{return con.empty();}size_t size() const{return con.size();}const T top() const{return con.front();}void push(const T val){con.push_back(val);adjustup(con.size() - 1);}void pop(){std::swap(con.front(), con.back());con.pop_back();adjustdown(0);}void swap(priority_queue x){con.swap(x.con);}Self operator(Self x){con x.con;comp x.comp;return *this;}private:void adjustdown(int pos)//向下调整{int parent pos;int child parent * 2 1;if (child 1 con.size() comp(con[child] , con[child 1])) child;while(child con.size()){if (comp(con[parent], con[child])){std::swap(con[child], con[parent]);parent child;child parent * 2 1;if (child 1 con.size() comp(con[child], con[child 1])) child;}else{break;}}}void adjustup(int pos)//向上调整{int child pos;int parent (child 1) / 2 - 1;while (parent 0){if (comp(con[parent], con[child])){std::swap(con[child], con[parent]);child parent;parent (child 1) / 2 - 1;}else{break;}}}container con;compare comp;};
}仿函数函数对象是什么
仿函数又称函数对象是指其本质虽然是对象但是用起来就像函数一样一个简单的仿函数长下面这样
templateclass T
class compareruler
{bool operator()(const T a, const T b){return a b;}
};仿函数通过重载()运算符使其使用起来就像函数一样依旧以上面这个仿函数为例它的用法如下 comparerulerint com;int a 0;int b 1;cout com(a, b) endl;不看上面的对象初始化就会误以为com是函数了。这就是仿函数那说了这么多仿函数有什么用呢学习过模板的都知道c提倡泛型编程即一段代码多种用途通过模板与模板实例化使一段代码生成多段代码鼓励用户自定义提高编程效率。而仿函数更是使泛型编程更进一步仿函数可以自定义模板编程中的策略模式使用户使用起来更加自由比如在堆的实现过程中就可以自定义两数之间的比较交换规则实现大堆小堆的切换这也是我提前介绍一下仿函数的原因。
向上调整算法adjustup
void adjustup(int pos)//向上调整
{int child pos;int parent (child 1) / 2 - 1;while (parent 0){if (comp(con[parent], con[child])){std::swap(con[child], con[parent]);child parent;parent (child 1) / 2 - 1;}else{break;}}
}向上调整算法是堆的核心算法之一其原理是将指定元素通过与其父结点比较若不符合当前堆的排列规则大堆小堆就交换符合就停止不断地循环这个过程直到根节点从而将指定元素排到合适的位置。具体的实现过程就是先指定结点将指定的结点视为子节点算出子结点的父节点将两者进行比较比较逻辑由仿函数给出。若仿函数返回true就交换之后将换完的父节点视为子节点再次计算父节点不断循环若仿函数返回false就说明到合适的位置了停止循环即可。过程中要时刻注意越界问题。
向下调整算法adjustdown
void adjustdown(int pos)//向下调整
{int parent pos;int child parent * 2 1;if (child 1 con.size() comp(con[child] , con[child 1])) child;while(child con.size()){if (comp(con[parent], con[child])){std::swap(con[child], con[parent]);parent child;child parent * 2 1;if (child 1 con.size() comp(con[child], con[child 1])) child;}else{break;}}
}向下调整算法也是堆的核心算法之一其原理是将指定元素通过与其最大的大堆小堆相反子结点比较若不符合当前堆的排列规则大堆小堆就交换符合就停止不断地循环这个过程直到不能向下为止从而将指定元素排到合适的位置。具体的实现过程就是先指定结点将指定的结点视为父节点算出父结点的子节点中最大的一个将两者进行比较比较逻辑由仿函数给出。若仿函数返回true就交换之后将换完的子节点视为父节点再次计算子节点不断循环若仿函数返回false就说明到合适的位置了停止循环即可。过程中要时刻注意越界问题。
迭代器构造 templateclass Iteratorpriority_queue(Iterator begin, Iterator end){Iterator cur begin;while (cur ! end) con.push_back(*(cur));int pos size() / 2 - 1;while (pos 0) adjustdown(pos--);}迭代其构造的思路有两种一种是先全部拷进堆中再排序第二种是一个个push进去。效率差不多我使用的第一种因为难写一点使用第一种写法需要注意使用向下调整算法比向上调整更优秀。为什么呢使用向上调整算法就要从最上方也就是根节点开始把推遍历一遍才行而使用向下调整算法则反之要从堆的最下面的最后一个元素开始遍历对一遍。其中向上和向下的算法中单趟的时间复杂度都是logN,这样看来两者都是一样的但是注意两者都是有优化的空间的。当使用向上调整算法时根节点因为没有父结点所以没有比的必要可以优化掉一个而使用向下调整算法时最下面一排的元素满二叉树就是最下面一排不是满二叉树就是最下面一排加最下面第二排部分反正就是没有子节点的结点也就是叶子节点因为没有子节点所以也没有比的必要可以优化掉整整一排要知道最后一排的结点数占了二叉树差不多一半优化巨大所以要用向下调整算法从最后一个有子结点的结点开始遍历找这个结点的方式也很简单最后一个有子结点的结点就是最后一个元素的父结点。
push
void push(const T val)
{con.push_back(val);adjustup(con.size() - 1);
}先入到容器的结尾再用向上调整算法跳到合适的位置就行。
pop
void pop()
{std::swap(con.front(), con.back());con.pop_back();adjustdown(0);
}由于我们这的堆是依靠容器中的位置模拟的二叉树所以对于相对位置有着强逻辑堆顶的元素不能直接头删我们先将堆顶元素与最后一个元素交换之后尾删相当于删除堆顶在找了个替位的之后对堆顶这个替位的使用向下调整算法调到合适的位置就行了。
由于priority_queue本质是一个容器适配器其他的函数就只是对适配器接口的一些封装了很简单这里不过多赘述。
