優先隊列的一種實現方式—堆

場景

在做一個APP的聊天功能，聊天消息走socket推過來的，每個消息有唯一的id，id隨時間是增大的，聊天消息要按時間有序，不重復，不遺漏。

不遺漏：一種方式就是本地保存最新的消息id，請求最新數據時帶上這個id，等到請求回來，才能更新最新id，注意一下邊界開區間閉區間的問題就可以了，服務器應該返回 ( 本地最新id, 服務器最新id ]，這種左開右閉的區間給客戶端就行。

不重復：有時候移動網絡很差，一個請求發出去很久才響應，中間可能隔了幾秒鐘，這個時候，有些用戶很急可能會狂點界面，比如我，導致請求重復發（實際中已做限頻，狂點也不會發請求），然后回來的消息自然就有很多重復了。去重很簡單了，OC 中用 NSMutableDictionary，底層是哈希表，把消息id 作為 key，加入到字典中再拿出來，重復的就沒有了。但實際中數據量較小，你寫兩個 for 循環去重也不會有什么性能問題，理論上會更耗cpu和電量。

消息有序

第一的想法是每次收到新的消息就加入到優先隊列中，然后一出隊就全部都是有序的了。但是 oc 中沒有優先隊列這種結構，甚至連隊列都沒有，一個變通的做法就是用 NSMutableArray 來實現隊列和棧，但是用法很別扭，如果 NSMutableArray 用數組實現的話，會有大量的位移操作，效率會很低。

一開始我把消息保存到 NSArray 中，每次來了新消息都執行排序+去重的操作來保證有序，數據量小就沒什么問題，其實也不小，群里面聊天幾十個人同時發消息，一下就重復好多次這樣的操作。后來比較有空，就自己用 oc 實現了一個優先隊列，方便使用，效率高，大量數據下性能也很好。

優先隊列

普通隊列是先進先出的結構，優先隊列是一種按照優先級大小，比如小的先出隊，的一種結構。所以先進的不一定先出，它會把優先級高的先出，下面我認為id小的優先級高。要先出隊。

舉個例子

入隊元素順序：2, 3, 4, 5, 1
 
普通隊列出隊：2, 3, 4, 5, 1
優先隊列出隊：1, 2, 3, 4, 5  (有序)

那么如何實現優先隊列？有以下三種方法

1.入隊有序

就是每加入一個元素的時候，把它移到一個“合適”的位置，舉個例子

隊列中已經有 1, 3, 4，現在要加入 2
那么把 2 移到 1，3 的中間，就是 1, 2, 3, 4
這個“合適”的位置定義為：前一個元素 

入隊已經保證有序了，那么出隊就直接把第一個元素拿出來，就是最小的了。

顯然 n 個元素的時間復雜度，入隊操作 O(n)，出隊操作 O(1)

缺點：該方法，如果有大量的入隊操作比較耗時。

2.遍歷最小的出隊

因為方法1的入隊操作耗時，那么方法2做了個改進，入隊的時候什么也不做，直接追加到尾部，出隊時候去遍歷數組中最小的元素出隊，舉個例子。

隊列中已經有 3, 1, 4，現在要加入 2
那么把 2 加到尾部，就是 3, 1, 4, 2

出隊的時候，遍歷數組，找到最小的元素1，出隊就行了

顯然，入隊操作 O(1)，出隊操作 O(n)

缺點：如果有大量出隊操作比較耗時

3.二叉堆

由于上面兩種方法都有缺點，最后用 堆 這種數據結構來實現優先隊列

什么是堆？

如下圖

heap

入隊操作，向堆中加入一個元素

add

出隊操作，從堆中刪掉一個元素

del

用堆來實現優先隊列，入隊，出隊操作復雜度 O(log n)，比較平衡。

 

 

來自：http://ios.jobbole.com/90773/