付第三期网站建设费的账务处理,wordpress漏洞视频,关键词优化推广公司,十堰市住房和城乡建设厅官方网站一.堆的概念
1.1 堆是什么 堆也叫做优先队列#xff0c;一些按照重要性或优先级来组织的对象称为优先队列。
1.2 为什么需要堆 在现实生活中#xff0c;存在许多需要从一群人、一些任务或一些对象中找出“下一位最重要”目标的情况。例如#xff1a;在平时处理事情的时候我…一.堆的概念
1.1 堆是什么 堆也叫做优先队列一些按照重要性或优先级来组织的对象称为优先队列。
1.2 为什么需要堆 在现实生活中存在许多需要从一群人、一些任务或一些对象中找出“下一位最重要”目标的情况。例如在平时处理事情的时候我们总会先把“下一个最重要的”的事情取出来先处理。在处理的过程中可能还会有其他的事情加进来。因此在事情处理完的事情我们又要重新找出“下一个最重要”的事情进行处理。 堆就是处理这种情况的我们通常把堆中的数据按照一定的重要性进行排序从而按照顺序一个个取出堆中的元素。
1.3 如何创建一个堆 通常来说我们容易想到以下的方法 对所有元素进行一次排序然后取出最大值。但这种方法不是很好。它多做了很多无用功。因为其实我可能只要取一个最大值就OK了但是却画蛇添足地帮我把所有元素都排好序了。很浪费时间。排序的时间复杂度至少为O(nlogn),插入和删除操作的时间复杂度为O(n)。 而理论上我们所要实现的优先队列的时间复杂度是可以比这个更优的。
二.堆的属性
2.1 定义 堆是一棵近乎满二叉树我们可以用数组来实现这棵二叉树因为如果是满二叉树的话其极其符合数组的形式并且节点也可以用下标来表示下面会证明。堆中的数据是局部有序的。我们使节点储存的值和它的子节点之间存在某种关系,从而利用数组模拟出堆这种形式。 2.2 堆的类型 最大值堆任意一个节点的值都大于它的子节点的值这样根节点存储的就是这组数据的最大值。最小值堆任意一个节点的值都小于它的子节点的值这样子根节点存储的就是这组数据的最小值。 2.3 堆的特殊规律 既然堆的逻辑结构是完全二叉树那么它就同样具有完全二叉树的性质 。 对于完全二叉树若从上至下、从左至右编号以根节点为0开始则编号为i的节点其左孩子节点编号为2i1右孩子节点编号为2i2父亲节点为 (i-1) / 2。 这个规律非常重要 验证 一棵节点个数为N的完全二叉树其高度为 h log 2 (N1)2为底数。 三.堆的实现
3.1 堆的基本结构 我们在上面讲解了对于一个满二叉树形式的结构我们可以用一个数组来模拟,但有时候我们也可以用其它类型来进行模拟在库里面其实底层是一个模板参数堆可以根据传入的类型来更改底层类型不过默认为vector.
如下
namespace My {templateclass T, class Container vectorTclass Priority_queue {public:private:Container _con;};}
3.2 堆的向下调整算法 向下调整是让调整的结点与其孩子节点进行比较若想将其调整为小堆那么根结点的左右子树必须都为小堆若想将其调整为大堆那么根结点的左右子树必须都为大堆一般用于创建堆。 小根堆示例 向下调整算法的基本思想最小堆示例
从根结点处开始选出左右孩子中 值较小的孩子。让较小的孩子与其父亲进行比较。若小的孩子比父亲还小则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整直到调整到叶子结点为止。若小的孩子比父亲大则不需处理了调整完成整个树已经是小堆了。
注意这里我们的大根堆和小根堆的大小对比明显是完全不一样的那么我们就需要写两个向下调整代码吗 不不需要我们可以在创建一个对象时传入一个仿函数从而实现让用户自己来控制需要的堆。 模板修改 仿函数实现 //构建大根堆函数struct Less{bool operator()(int k1,int k2){return k1 k2;}};//构建小根堆函数struct Greater{bool operator()(int k1, int k2) {return k1 k2;}};//默认构建大根堆templateclass T,class KvalueLess
向下调整代码的实现
//在类外这个函数是完全不需要的因此设置为private
private:void adjust_down(int parent) {//构建仿函数Compare _com;int child parent * 2 1;while (child _con.size()) {//判断右节点有没有越界顺便求出两个节点较大值if (child 1 _con.size() _com(_con[child], _con[child 1])) {child;}//根据对应仿函数判断是否需要交换if (_com(_con[parent], _con[child])) {swap(_con[parent], _con[child]);parent child;child parent * 2 1;}//不符合仿函数判断条件直接返回else {break;}}}
3.3 堆的创建 我们都知道堆的底层结构是一个数组类型 那么我们除了让一个空堆一个个插入还能直接用一个数组来构建堆吗答案是完全可以。 那么我们该如何做呢 首先堆的底层结构就是一个数组类型那么我们可以直接用堆内的数组 copy 一下 传入的数组然后按照向下调整算法构建一个堆。 从上面的向下调整算法我们得知我们使用向下调整算法时需要保证左右两个子树都为堆因此单纯的从头节点开始向下调整是不可以的。 这里我们可以把最底层的节点看为一个个堆从最底层开始调整但是如果从最底层开始调节又有点太浪费资源这里建议 从最后一个父节点(size/2-1 的位置逐个往前调整所有父节点直到根节点,确保每一个父节点都是一个最大堆最后整体上形成一个最大堆 。 ps因为最后一个父节点最多只有两个子节点因此它的左右子树也必定是一个堆。 //在C 中 我们现在基本都用迭代器构造 因此创建一个迭代器模板类型template class InputIteratorPriority_queue(InputIterator first, InputIterator last):_con(first, last)//直接调用底层数据结构的迭代器构造{ //这里减2 的原因是 数组下标的问题 因为从0开始所以真正的大小应该减一在带入先前的算法for (int i (_con.size() - 2) / 2; i 0; i--) {adjust_down(i);}}
3.4 堆的向上调整代码 向上调整是让调整的结点与其父亲结点进行比较当我们已经有一个堆显然我们在头部插入数据会破坏原有的堆结构因此我们需要在堆的末尾插入数据再对其进行调整使其任然保持堆的结构这里我们就需要用到堆的向上调整算法。 向上调整算法的基本思想
将目标结点与其父结点比较若目标结点的值比其父结点的值大则交换目标结点与其父结点的位置将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大则停止向上调整此时该树已经是大堆了
代码示例
void adjust_up(int child) {Compare _com;int parent (child - 1) / 2;while (child 0) {if (_com(_con[parent], _con[child])) {swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else {break;}}
}
3.5 堆的插入 我们直接对数组进行尾插然后在插入位置向上调整因为插入时只改变插入位置到根这一条路径因此只向上调整一次即可。 代码示例 void push(const T x) {_con.push_back(x);adjust_up(_con.size() - 1);}
3.6 堆的删除 堆的删除这里我们有特殊的规则像我们直接删掉尾部的数据其实是不改变堆的结构的但那样有意义吗 堆本来就起到一个排序的作用你怎么知道最后一位数据到底是多少呢堆只能取到头部的顺序因此在我们删除时是删除头部的数据。 但是直接删除的话会把我们的堆结构变得极其混乱对此我们提出了另一种解法 我们把头元素和尾部元素进行一次交换然后把新尾部删除让新头部元素向下调整这样交换后头元素的左右依旧是堆结构只需要一次调整就能得到一个新堆。 代码如下 void pop() {swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}
3.7 其它接口 bool empty() const {return _con.empty();}size_t size() const {return _con.size();} 四.代码测试
oid test1() {My::Priority_queue int pq1;pq1.push(5);pq1.push(2);pq1.push(3);pq1.push(9);pq1.push(4);while (!pq1.empty()) {cout pq1.top() endl;pq1.pop();}}void test2(){vectorint v1 { 1,3,4,5,8,10,12 };Priority_queueint q1(v1.begin(), v1.end());Priority_queueint, vectorint, Greaterint q2(v1.begin(), v1.end());cout size: q1.size() endl;while (!q1.empty()){cout q1.top() ;q1.pop();}cout endl;cout size: q2.size() endl;while (!q2.empty()){cout q2.top() ;q2.pop();}cout endl;}
答案 五.完整代码
My_Priority_Queue.h
#pragma once
#includeiostream
#includevectorusing namespace std;namespace My {templateclass Tstruct Less {bool operator()(const T t1, const T t2) {return t1 t2;}};templateclass Tstruct Greater {bool operator()(const T t1, const T t2) {return t1 t2;}};templateclass T, class Container vectorT, class Compare LessT class Priority_queue {public:Priority_queue() {}template class InputIteratorPriority_queue(InputIterator first, InputIterator last):_con(first, last){for (int i (_con.size() - 2) / 2; i 0; i--) {adjust_down(i);}}bool empty() const {return _con.empty();}size_t size() const {return _con.size();}void push(const T x) {_con.push_back(x);adjust_up(_con.size() - 1);}void pop() {swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T top() {return _con[0];}private:void adjust_down(int parent) {Compare _com;int child parent * 2 1;while (child _con.size()) {if (child 1 _con.size() _com(_con[child], _con[child 1])) {child;}if (_com(_con[parent], _con[child])) {swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else {break;}}}void adjust_up(int child) {Compare _com;int parent (child - 1) / 2;while (child 0) {if (_com(_con[parent], _con[child])) {swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else {break;}}}private:Container _con;};void test1() {My::Priority_queue int pq1;pq1.push(5);pq1.push(2);pq1.push(3);pq1.push(9);pq1.push(4);while (!pq1.empty()) {cout pq1.top() endl;pq1.pop();}}void test2(){vectorint v1 { 1,3,4,5,8,10,12 };Priority_queueint q1(v1.begin(), v1.end());Priority_queueint, vectorint, Greaterint q2(v1.begin(), v1.end());cout size: q1.size() endl;while (!q1.empty()){cout q1.top() ;q1.pop();}cout endl;cout size: q2.size() endl;while (!q2.empty()){cout q2.top() ;q2.pop();}cout endl;}
} test.cc
#includeMy_Priority_Queue.hint main() {try{My::test2();}catch (...){cout 未知异常 endl;}return 0;
}
