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.
