Я пытаюсь написать load-balancer в Haskell с минимальной стратегией (частично для удовольствия..). Мне нужна очередь приоритетов, где требуется только "следующие операции":
- прочитать минимальный ключ
- +1 на минимальном ключе
- -1 на любой клавише
Если бы у меня был императивный язык с указателями, я бы, вероятно, пришел с:
Head
|
Priority 0 -> Item <-> Item <-> Item <-> Item
|
Priority 1 -> Item <-> Item
|
Priority 4 -> Item <-> Item <-> Item
Приоритеты подключаются с использованием двусвязного списка, элементов для каждого приоритета. Каждый Item содержит ссылку на главный приоритет. Эта структура будет сложной:
- O (1) для минимального ключа для чтения. Возьмите сначала из очереди под головой.
- O (1) для +1 - удалить первый элемент под первым приоритетом, вставить его на более низкий уровень (возможно, создать новый уровень)
- O (1) для -1 - если у нас есть указатель на элемент, мы можем немедленно получить доступ к Приоритету, удалить элемент из дважды связанного списка и вставить его в другой
Есть ли какая-то (функциональная?) структура данных, которая будет вести себя примерно одинаково? Количество элементов будет составлять не более пары сотен.
