Java中如何从按字符串值排序的Priority Queue删除指定区间元素

绝大多数日常用到的优先队列，都是基于二叉堆结构实现的——这种结构只保证队头元素是全局优先级最高/最低的，内部存储的元素并不满足全局线性有序，也没有内置的范围定位能力，这也是做范围删除的核心难点。

通用无侵入实现（适配所有原生优先队列） #

如果你用的是语言标准库自带的PriorityQueue（比如Java、Python标准库的实现），不需要修改队列内部结构的话，直接全量筛选即可：

• 新建一个空的临时存储结构
• 把原优先队列的所有元素逐个弹出，判断元素值是否落在要删除的区间内：不在区间内的元素存到临时结构里，落在区间内的直接丢弃
• 清空原队列，把临时结构里留存的元素全部重新塞回原队列

这个方法写起来代码量极少，完全不需要理解优先队列的内部实现，哪怕队列的迭代器不保证有序遍历也不影响判断逻辑。举个Python场景的示例代码：

from queue import PriorityQueue
pq = PriorityQueue()
# 假设队列里已经存了A-Z的字符串元素
del_start, del_end = "M", "Q"
remain_items = []
# 全量筛选需要保留的元素
while not pq.empty():
    cur = pq.get()
    if not (del_start <= cur <= del_end):
        remain_items.append(cur)
# 把留存元素塞回原队列
for item in remain_items:
    pq.put(item)

这里要提个容易踩的大坑：千万别想着"连续弹出队头元素，直到弹出的值达到删除区间的起点，把区间内的元素弹完就把之前弹的小元素塞回去"——堆结构根本不保证所有小于区间起点的元素都排在队头路径上，这种操作极容易误删范围外的合法元素。

这个方法的时间复杂度是O(n log n)，因为要把留存的元素全部重新入队，在数据量不大（比如几千个元素以内）的场景下性能完全够用，是绝大多数场景下的首选实现。

大数据量下的高效实现 #

如果你的优先队列存了百万级以上的元素，全量重新入队的性能开销不可接受，就需要改造优先队列的结构，加上有序辅助索引：

• 除了原本存储元素的堆结构外，额外维护一个按元素值全局有序的平衡结构（比如跳表、红黑树），让堆里每个元素的位置和有序结构里的节点做双向绑定
• 做范围删除的时候，直接在有序结构里定位到[del_start, del_end]的区间，拿到区间内所有元素的绑定信息
• 给这些要删除的元素打惰性删除标记，不需要立刻从堆里移除，等后续弹出队头元素的时候，碰到带删除标记的元素直接跳过就行，最后把有序结构里对应的区间节点清掉即可

这个方案的时间复杂度是O(log n + k)，其中k是要删除的元素个数，性能远高于全量筛选的实现，只需要在高并发、大数据量的场景下使用即可。

对应示例场景的操作步骤 #

就拿存储A-Z、按升序排列的优先队列，删除M到Q区间元素的场景来说：

1. 用普通堆实现的话，全量遍历取出所有元素，把M、N、O、P、Q这几个区间内的元素丢弃，剩下的A-L、R-Z元素重新入队就完成了
2. 用带跳表索引的实现的话，直接在跳表里定位到M的位置，顺着节点遍历到Q，给这5个元素打删除标记，后续弹队头的时候自动跳过这些标记过的元素，完全不需要动剩下的元素。

实际开发的时候90%的情况根本不需要搞后面那套复杂结构，普通全量筛的方法三五行代码就能写完，性能完全够；真碰到性能瓶颈的时候再换改造过的实现也不迟。

内容的提问来源于stack exchange，提问作者Cheetos