首先啊先简单介绍一下优先队列的概念学数据结构以及出入算法竞赛的相信都对队列这一数据结构十分熟悉这是一个线性的数据结构.针对队列这一特殊数据结构有时需考虑队列元素的优先级的关系即根据用户自定义的优先级排序出队时优先弹出优先级更高(低)的元素优先队列能更好地满足实际问题中的需求而在优先队列的各种实现中堆是一种最高效的数据结构。什么是堆堆是一颗具有特定性质的二叉树堆的基本要求就是堆中所有结点的值必须大于或等于或小于或等于其孩子结点的值这也称为堆的性质我们也叫堆序性堆还有另一个性质就是当 h 0 时所有叶子结点都处于第 h 或 h - 1 层其中 h 为树的高度完全二叉树也就是说堆应该是一颗完全二叉树如下:根据两种堆序性我们将堆分为两类即根节点权值≥子节点权值的我们叫大根堆根节点权值≤子节点权值的我们叫小根堆。道理简单就不做图演示了。上文所述优先队列是由一个堆维护的堆序性正对应了优先队列的优先级。由此优先队列就并不是一个线性的数据结构其所有操作都是logn的时间复杂度。了解完堆与优先队列的关系我们就可以开始讨论如何实现优先对列了。堆的存储方式我们将一个堆从上到下从左到右(实际上这个顺序也是堆一般的讨论模式)从0开始给每个节点编号。如下图:然后按照顺序存储进一个线性的数组之中那么这就算存储好了~简不简单意不意外是不是最开始想到的是递归生成树但实际上因为堆序性的存在我们并不需要那么复杂的存储方式~同样的道理我们反过来用一个数组建堆也就是如上操作的逆操作而已。问题就来了如何用一个无序的数组来建堆呢这就要谈到维护堆序性的两种操作——上浮下沉。维护堆的方法1、上浮操作首先将一个无序的数组按下标标号然后开始进行前方所说的建堆操作我们建堆的过程便是主要用到上浮操作每操作一步就要与父节点比较如果大于此处以大根堆为例子父节点则与父节点进行交换然后跳转到交换后的位置继续与父节点进行比较直到不大于父节点后就算完成了一次调整。光说肯定有些童鞋无法想象得那么明白下面放图这里用数组a[6] {3,5,8,9,1,2}做模板别多想很随机的数字罢了。第一步将下标为0的节点做根节点就是3啦~第二步将下标为1的节点也就是5作为3的左孩子~很明显啊5要比它的父节点3要大那么交换位置~再看5并没有比它小的根节点了那么继续下一步~第三步将下标为2的节点也就是8放在5的下边作为右孩子~很明显哦8比它的父节点大那么~交换位置~很明显8并没有比它更小的父节点了那么继续下一步~再接下去我就不讲了很简单序号从上到下从左到右。那么任一的一个节点如果它足够大小就一定会最底下一层爬到最大的根节点是不是上浮呢生动而形象在建堆的时候每插入一个元素就要对该元素进行一次上浮调整将其放在正确的地方。相信聪明的童鞋已经发现了同层的节点不存在任何的关系甚至不同根节点的同层节点也不存在任何关系每一个节点仅仅只是在其子堆中的最大值即局部最大值。2、下沉操作该操作在队列的基本操作也就是弹出队顶操作时所用即删除最大小根节点的操作。原理也很简单将编号为0的节点与编号最大的节点权值互换然后弹出编号最大的节点此时即前一步的队顶元素此时再对队顶节点进行下沉操作:先与左子树进行比较按照堆序性交换直到换回它应在的位置此时所有局部均为优先队列其也维护完成。上图:这里还是前面那个数组顺便也给大家看看建堆后的亚子~a[6] {3,5,8,9,1,2}第一步将编号为0的节点与编号最大的节点权值互换即将9与2进行互换。第二步弹出编号最大的节点此时即前一步的队顶元素即9第三步对队顶节点进行下沉操作即先和85进行顺序比较按照优先级明显与8互换换完后如下再与3先比较无法交换再与1比较~最后应该是这个样子的。两种操作方式也已经说完这里就会有童鞋问道那么如何在数组中进行所谓的上浮下沉操作呢这里就有一个很重要的知识了就是父节点和子节点在数组编号中的关系其实也并不难发现根据堆的性质有如下的关系设某个节点编号为i其父节点:dad (i - 1) / 2左/右子节点:left 2 * i 1right 2 * i 2这样大家就可以将上浮、下沉操作的每一步在数组中实现了附上代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173#includeiostream#includecmath#includestdlib.h#define bug coutnug is hereendl;#includevectorusingnamespacestd;typedefsize_tull;//堆templatetypenamePclassHeap{private:vectorint heap_elem;//堆容器ull heap_depth;//深度boolPriority;//优先级ull heap_size;//容量voidUp_adjust(intnow);//上浮调整voidDown_adjust(intnow);//下沉调整//now指代下标public://构造堆enum{max_heap true, min_heap false};Heap(vectorP l,boolpriority max_heap){heap_size l.size();heap_depth log2(heap_size);Priority priority;//设置优先级for(inti 0;i heap_size;i){heap_elem.push_back(l[i]);Up_adjust(i);//上浮调整}}Heap(inta[], ull n,boolpriority max_heap){heap_size n;heap_depth log2(heap_size);Priority priority;//设置优先级for(inti 0;i n;i){heap_elem.push_back(a[i]);Up_adjust(i);//上浮调整}}Heap(){heap_size 0;heap_depth 0;Priority max_heap;};//堆的成员函数ull Depth(){returnheap_depth;}ull Size(){returnheap_size;}voidPush(P x){heap_elem.push_back(x);heap_size;heap_depth log2(heap_size);swap(heap_elem[heap_elem.size() - 1], heap_elem[heap_size - 1]);//将加入的元素放入有效位Up_adjust(heap_size - 1);}voidPop(){heap_depth log2(heap_size);swap(heap_elem[--heap_size], heap_elem[0]);//将第一个元素与最后一个元素交换并且缩短有效位数//其实这里可以用vector的函数pop_back,相应的上面的Push函数也不用换位置但是这样更快Down_adjust(0);}P Top(){returnheap_elem[0];}voidshow_as_tree(){//以树的形式输出int_size max(log10(heap_elem[0]),log10(heap_elem[heap_size - 1])) 1;ull max_size (pow(2, heap_depth) * 2) * _size;ull _max_size _size *pow(2, heap_depth 1);intstart -1;for(inti 0;i heap_depth;i){max_size 1;max_size;if(i heap_depth) coutheap_elem[start];elseprintf(%*d,max_size,heap_elem[start]);intw pow(2, i);for(intj 1;j w start heap_size - 1;j)printf(%*d,_max_size,heap_elem[start]);_max_size 1;_max_size;printf(\n);}}voidshow_as_array(){//数组方式输出for(inti 0;i heap_size;i) coutheap_elem[i] ;coutendl;}};//上浮调整templatetypenamePvoidHeapP::Up_adjust(intnow){if(Priority)while(now 0 heap_elem[now] heap_elem[(now - 1) / 2]){//如果当前节点的权值比父亲大swap(heap_elem[now], heap_elem[(now - 1) / 2]);//交换now (now - 1) / 2;}elsewhile(now 0 heap_elem[now] heap_elem[(now - 1) / 2]){swap(heap_elem[now], heap_elem[(now - 1) / 2]);now (now - 1) / 2;}}//下沉调整templatetypenamePvoidHeapP::Down_adjust(intnow){ull left now * 2 1;ull right;while(left heap_size){//能换的时候left now * 2 1;right now * 2 2;if(Priority){if(heap_elem[now] heap_elem[left]){//比左孩子小下沉swap(heap_elem[now], heap_elem[left]);now left;}elseif(right heap_size){//比右孩子小下沉if(heap_elem[now] heap_elem[right]){swap(heap_elem[now], heap_elem[right]);now right;}}}else{if(heap_elem[now] heap_elem[left]){//比左孩子大下沉swap(heap_elem[now], heap_elem[left]);now left;}elseif(right heap_size){//比右孩子大下沉if(heap_elem[now] heap_elem[right]){swap(heap_elem[now], heap_elem[right]);now right;}}}}}intmain(){inta[6] {3,5,8,9,1,2};Heapint h(a, 6,true);//输出堆h.show_as_tree();// h.Push(12);// h.show_as_tree();//// h.Pop();// h.show_as_tree();//// couth.Top()endl;// vectorint a;// Heapint h(a, Heapint::max_heap);// for(int i0;i 10;i)// h.Push(rand()%100);//// h.show_as_tree();return0;}按照前面那个数组运行结果如下:是不是很神奇呢