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.

Answer 1

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!