文章目录
- 前言
- 一、优先队列
- 二、应用场景
- 三、代码实现
- 总结
前言
之前写过很多数据结构与算法相关的了，今天看一个新的数据结构，优先队列。优先队列类似队列，却又优先于队列，是堆实现的。接下来详细看看。
一、优先队列
优先队列一种特殊的队列。在优先队列中，元素被赋予优先级，当访问队列元素时，具有最高优先级的元素最先删除；
普通队列就是先进先出的。
二、应用场景
这个太多了，最经典的就是top k元素，将所有元素放进一个优先队列中，然后一个一个出来，到第K个，就是第K大元素了。接下来看看stl怎么实现的。
三、代码实现
上图是stl的实现。看红色框中的代码，主要有入队，出队操作;
这个是push_heap，入队操作；接下来看看出队pop_heap，如下：
看下上图，七个步骤，出队操作。最后又执行了一个__push_heap。这个写的挺简洁的。通用的模板，很多地方都在用。思考程度非一般人可比。
总结
优先队列，一个高于普通队列的数据结构，按照优先级排序，每次放进去一个数据，都要看下优先级，这就是adjust_heap的作用。入队，按照优先级调整；出队，也要按照优先级调整；这个代码的实现是基于它的特性确定的。很简洁了。好好学习学习。如果实在有疑惑，可以去学习网站看看，有可能就能解决了呢！嘿嘿。OK，翻篇。
