数据结构设计的问题，关于数据的接收与计数

Question

现在有一种这样的业务，要求设计一个合适的数据结构去表示（不是习题，是我工作中遇到的）

A是发送者，B是接收者
A在一段时间内会一直给B发包，包上面有包号：1,2,3,4单调递增
B在接收到之后，要一直记录这些包号，1,2,3,4

有可能B接收的包号不是递增的，比如1,2,4,7. 然后3,5,6未必能接收到

1. B最多记录256个包号

2. B经常需要从接收到的包里面取出最大的包号，比如7

3. B有时候需要删除小于某个包号的一系列包。比如要删除5, 那么B接收到的包号就变成7，以后再接收到4，也会忽略。

4. 如果B收到两个一样的包号，那要报异常

对于以上的业务，可以设计一种怎么样的数据结构去存储？
我目前的想法是用最大堆，B每收到一个包就加进去堆里面，堆顶元素就是最大的包号。
对于删除，只能想到先排序再二分定位，把剩下的元素再构建一个最大堆。但无法做到“以后再接收到4，也会忽略”
无法识别两个一样的包号

也有想过直接用一个256长度的数组，另外增加一个最大包号和最小包号的变量
每收到一个包，就在数组相应的位置增加一个记录，并更新最大包号和最小包号的变量
要删除5，就把B里面所有大于5的号往前挪位置
很容易识别两个一样的包号

但总感觉后面的方法太笨了，有无更好的数据结构可以支持这样的操作？

Answer 1

要不要考虑一下线段树，对基础的线段数做一下拓展。

Answer 2

我看了几遍你的描述，有些地方还是不太理解。
但就你给出的某些要求，我建议用平衡二叉搜索树（BBST）——AVL树，红黑树等等

1. B最多记录256个包号

   • BBST中包含的节点数——size()接口，O(1)

2. B经常需要从接收到的包里面取出最大的包号

   • 大顶堆用O(1)，BBST略差需要用O(logN)

   • 理论：BBST中任意节点R，其左子树中所有节点的值均小于R->val，其右子树中所有节点的值均大于R->val。

   • 实现:从根节点开始一直向右找，直到X->right_child == NULL则返回X->val即可

3. 如果B收到两个一样的包号，那要报异常

   • 基于BBST标准的find接口即可，O(logN)

   • find(val)，获取到包含val的节点K

   • 如果find(val) == NULL将val插入BBST，否则（找到包含val的节点）报错

4. B有时候需要删除小于某个包号的一系列包

   • 用find(val)确定包号，O(logN)

   • 删除包含val的节点K的所有左子树中的节点即可

   • 注意，不要直接K->left_child = NULL（将K的左子树删除，这样可能导致树的倾斜）

     • BBST标准delete接口通常包含再平衡操作即每删除一个节点，就调整一次，时间为O(logN)

     • 所以删除小于某个包号的一系列包，时间复杂度为O(mlogN),m为小于某个包的一系列
       包的个数

     • 最坏情况，删除小于最大包号的一系列包，O(NlogN)