数据结构与算法===优先队列

前言

之前写过很多数据结构与算法相关的了，今天看一个新的数据结构，优先队列。优先队列类似队列，却又优先于队列，是堆实现的。接下来详细看看。

一、优先队列

优先队列一种特殊的队列。在优先队列中，元素被赋予优先级，当访问队列元素时，具有最高优先级的元素最先删除；
普通队列就是先进先出的。

二、应用场景

这个太多了，最经典的就是top k元素，将所有元素放进一个优先队列中，然后一个一个出来，到第K个，就是第K大元素了。接下来看看stl怎么实现的。

三、代码实现

上图是stl的实现。看红色框中的代码，主要有入队，出队操作;

这个是push_heap，入队操作；接下来看看出队pop_heap，如下：

看下上图，七个步骤，出队操作。最后又执行了一个__push_heap。这个写的挺简洁的。通用的模板，很多地方都在用。思考程度非一般人可比。

总结

优先队列，一个高于普通队列的数据结构，按照优先级排序，每次放进去一个数据，都要看下优先级，这就是adjust_heap的作用。入队，按照优先级调整；出队，也要按照优先级调整；这个代码的实现是基于它的特性确定的。很简洁了。好好学习学习。如果实在有疑惑，可以去学习网站看看，有可能就能解决了呢！嘿嘿。OK，翻篇。