Fast priority queue with incremental updates

Question

I am trying to write a load-balancer in Haskell with leastconn strategy (partly for fun..). I need a priority queue where only the following operations are required to be 'fast':

read minimum key
+1 on minimum key
-1 on any key

If I had an imperative language with pointers, I would probably come with:

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

Priorities are connected using a doubly linked list, the items for every priority too. Each Item contains a link to the head Priority. This structure would have complexity:

O(1) for read minimum key - Take first from queue under head
O(1) for +1 - remove first item under first priority, insert it on lower level (possibly creating a new level)
O(1) for -1 - provided we have a pointer to the item, we can immediately access the Priority, remove the item from doubly linked list and insert it into a different one

Is there some (functional?) data structure that would behave approximately the same? The number of items would be approximately at most a couple of hundreds.

I think it is a pretty established fact that you can't have all of the priority queue operations O(1). Whereas the "insertion" or "removal" as such are cheap, the cost appears when you consider the time to find the spot to insert or remove from, and the effort to re-balance (maintain sorted). — Sassa NF
Sassa, this is true for generic heaps, but when I limit the operations to +/-1, i can update the priority just by moving it up or down the priority list from a known level and that is O(1) — ondra
@ondra perhaps that's not the priority queue; that's N FIFO queues — Sassa NF

sclv sclv · Accepted Answer · 2015-02-20T04:03:12

It sounds to me like the common structure which suits your needs is a Priority Search Queue as described in Hinze (2001). One of the better hackage packages providing such a structure is here: http://hackage.haskell.org/package/psqueues

This is perhaps not tuned exactly for your workflow, but it certainly isn't shabby!

Fast priority queue with incremental updates

1 Answers