具有增量更新的快速优先级队列

Question

我试图用最少的策略在Haskell中编写负载均衡器(部分是为了好玩......).我需要一个优先级队列,其中只需要以下操作"快速":

• 读取最小键
• +1最小密钥
• -1在任何键上

如果我有一个带指针的命令式语言,我可能会带来:

Head
  |
Priority 0 -> Item <-> Item <-> Item <-> Item
  |
Priority 1 -> Item <-> Item
  |
Priority 4 -> Item <-> Item <-> Item

优先级使用双向链表连接,每个优先级的项目也是如此.每个都Item包含指向头部优先级的链接.这种结构会有复杂性:

• O(1)用于读取最小键 - 从头部队列中取出
• O(1)for +1 - 删除第一优先级下的第一个项目,将其插入较低级别(可能创建一个新级别)
• O(1)为-1 - 如果我们有一个指向该项的指针,我们可以立即访问优先级,从双向链表中删除该项并将其插入另一个

是否存在一些行为大致相同的(功能？)数据结构？物品数量最多约为几百个.

Answer 1

在我看来，适合您需求的通用结构是Hinze (2001)中描述的优先级搜索队列。提供这种结构的更好的黑客包之一在这里：http ://hackage.haskell.org/package/psqueues

这可能没有完全适合您的工作流程，但它肯定不破旧！