优先队列的一种实现方式—堆

   <p>场景</p>    <p>在做一个APP的聊天功能，聊天消息走socket推过来的，每个消息有唯一的id，id随时间是增大的，聊天消息要按时间有序，不重复，不遗漏。</p>    <p><strong>不遗漏</strong>：一种方式就是本地保存最新的消息id，请求最新数据时带上这个id，等到请求回来，才能更新最新id，注意一下边界开区间闭区间的问题就可以了，服务器应该返回 ( 本地最新id, 服务器最新id ]，这种左开右闭的区间给客户端就行。</p>    <p>不重复：有时候移动网络很差，一个请求发出去很久才响应，中间可能隔了几秒钟，这个时候，有些用户很急可能会狂点界面，比如我，导致请求重复发（实际中已做限频，狂点也不会发请求），然后回来的消息自然就有很多重复了。去重很简单了，OC 中用 NSMutableDictionary，底层是哈希表，把消息id 作为 key，加入到字典中再拿出来，重复的就没有了。但实际中数据量较小，你写两个 for 循环去重也不会有什么性能问题，理论上会更耗cpu和电量。</p>    <h2><strong>消息有序</strong></h2>    <p>第一的想法是每次收到新的消息就加入到优先队列中，然后一出队就全部都是有序的了。但是 oc 中没有优先队列这种结构，甚至连队列都没有，一个变通的做法就是用 NSMutableArray 来实现队列和栈，但是用法很别扭，如果 NSMutableArray 用数组实现的话，会有大量的位移操作，效率会很低。</p>    <p>一开始我把消息保存到 NSArray 中，每次来了新消息都执行排序+去重的操作来保证有序，数据量小就没什么问题，其实也不小，群里面聊天几十个人同时发消息，一下就重复好多次这样的操作。后来比较有空，就自己用 oc 实现了一个优先队列，方便使用，效率高，大量数据下性能也很好。</p>    <h2><strong>优先队列</strong></h2>    <p>普通队列是先进先出的结构，优先队列是一种按照优先级大小，比如小的先出队，的一种结构。所以先进的不一定先出，它会把优先级高的先出，下面我认为id小的优先级高。要先出队。</p>    <p>举个例子</p>    <pre>  入队元素顺序：2, 3, 4, 5, 1     普通队列出队：2, 3, 4, 5, 1  优先队列出队：1, 2, 3, 4, 5  (有序)  </pre>    <p>那么如何实现优先队列？有以下三种方法</p>    <h3><strong>1.入队有序</strong></h3>    <p>就是每加入一个元素的时候，把它移到一个“合适”的位置，举个例子</p>    <pre>  队列中已经有 1, 3, 4，现在要加入 2  那么把 2 移到 1，3 的中间，就是 1, 2, 3, 4  这个“合适”的位置定义为：前一个元素   </pre>    <p>入队已经保证有序了，那么出队就直接把第一个元素拿出来，就是最小的了。</p>    <p>显然 n 个元素的时间复杂度，入队操作 O(n)，出队操作 O(1)</p>    <p>缺点：该方法，如果有大量的入队操作比较耗时。</p>    <h3><strong>2.遍历最小的出队</strong></h3>    <p>因为方法1的入队操作耗时，那么方法2做了个改进，入队的时候什么也不做，直接追加到尾部，出队时候去遍历数组中最小的元素出队，举个例子。</p>    <pre>  队列中已经有 3, 1, 4，现在要加入 2  那么把 2 加到尾部，就是 3, 1, 4, 2  </pre>    <p>出队的时候，遍历数组，找到最小的元素1，出队就行了</p>    <p>显然，入队操作 O(1)，出队操作 O(n)</p>    <p>缺点：如果有大量出队操作比较耗时</p>    <h3><strong>3.二叉堆</strong></h3>    <p>由于上面两种方法都有缺点，最后用 <strong>堆</strong> 这种数据结构来实现优先队列</p>    <p><strong>什么是堆？</strong></p>    <p>如下图</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/ad21c1dd3a8eb0a9927c17d4f6977dcc.jpg"></p>    <p><strong>heap</strong></p>    <p>入队操作，向堆中加入一个元素</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/efd220aa0a43c388f7963350caea3ace.jpg"></p>    <p><strong>add</strong></p>    <p>出队操作，从堆中删掉一个元素</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/b58a732e7be6c4392ca6c8c9bab5454a.jpg"></p>    <p><strong>del</strong></p>    <p>用堆来实现优先队列，入队，出队操作复杂度 O(log n)，比较平衡。</p>    <p> </p>    <p> </p>    <p>来自：http://ios.jobbole.com/90773/</p>    <p> </p>