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

场景

在做一个APP的聊天功能,聊天消息走socket推过来的,每个消息有唯一的id,id随时间是增大的,聊天消息要按时间有序,不重复,不遗漏。

本博客主要想说消息有序,但提到了不重复,不遗漏,也简单说一下。
不遗漏:一种方式就是本地保存最新的消息id,请求最新数据时带上这个id,等到请求回来,才能更新最新id,注意一下边界开区间闭区间的问题就可以了,服务器应该返回 ( 本地最新id, 服务器最新id ],这种左开右闭的区间给客户端就行。还有一种保证消息100%到达的应用层应答机制,可以在我之前的博客看到点击查看

不重复:有时候移动网络很差,一个请求发出去很久才响应,中间可能隔了几秒钟,这个时候,有些用户很急可能会狂点界面,比如我,导致请求重复发(实际中已做限频,狂点也不会发请求),然后回来的消息自然就有很多重复了。去重很简单了,OC 中用 NSMutableDictionary,底层是哈希表,把消息id 作为 key,加入到字典中再拿出来,重复的就没有了。但实际中数据量较小,你写两个 for 循环去重也不会有什么性能问题,理论上会更耗cpu和电量。

消息有序

第一的想法是每次收到新的消息就加入到优先队列中,然后一出队就全部都是有序的了。但是 oc 中没有优先队列这种结构,甚至连队列都没有,一个变通的做法就是用 NSMutableArray 来实现队列和栈,但是用法很别扭,如果 NSMutableArray 用数组实现的话,会有大量的位移操作,效率会很低。

一开始我把消息保存到 NSArray 中,每次来了新消息都执行排序+去重的操作来保证有序,数据量小就没什么问题,其实也不小,群里面聊天几十个人同时发消息,一下就重复好多次这样的操作。后来比较有空,就自己用 oc 实现了一个优先队列,方便使用,效率高,大量数据下性能也很好。

优先队列

普通队列是先进先出的结构,优先队列是一种按照优先级大小,比如小的先出队,的一种结构。所以先进的不一定先出,它会把优先级高的先出,下面我认为id小的优先级高。要先出队。

举个例子

那么如何实现优先队列?有以下三种方法

1.入队有序

就是每加入一个元素的时候,把它移到一个“合适”的位置,举个例子

入队已经保证有序了,那么出队就直接把第一个元素拿出来,就是最小的了。
显然 n 个元素的时间复杂度,入队操作 O(n),出队操作 O(1)
缺点:该方法,如果有大量的入队操作比较耗时。

2.遍历最小的出队

因为方法1的入队操作耗时,那么方法2做了个改进,入队的时候什么也不做,直接追加到尾部,出队时候去遍历数组中最小的元素出队,举个例子。

出队的时候,遍历数组,找到最小的元素1,出队就行了
显然,入队操作 O(1),出队操作 O(n)
缺点:如果有大量出队操作比较耗时

3.二叉堆

由于上面两种方法都有缺点,最后用这种数据结构来实现优先队列

什么是堆?

如下图

112764502-2ee3dc6c142c9e90

heap

入队操作,向堆中加入一个元素

122764502-e93110fa7478b723

add

出队操作,从堆中删掉一个元素

132764502-833c0d3248547a8b

del

用堆来实现优先队列,入队,出队操作复杂度 O(log n),比较平衡。

最后还是上个 oc 写的代码吧(下载地址),顺便吐槽一下 c++, java 都 priority_queue 这样的数据结构,oc 居然没有,得自己用 NSMutableArray 模拟,或者自己写一个。

2 3 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部