Приоритетная очередь F#

Взгляните на http://lepensemoi.free.fr/index.php/tag/data-structure , где есть множество реализаций различных структур данных на F #. .

С F # вы можете использовать любую библиотеку .NET, поэтому, если вас устраивает реализация, которая не написана на F #, I Wintellect Power Collection Library.

Просто используйте F # Set пар вашего типа элемента с уникальным int (для разрешения дублирования) и извлеките свои элементы с помощью set.MinElement или set.MaxElement . Все соответствующие операции имеют временную сложность O (log n). Если вам действительно нужен повторный доступ O (1) к минимальному элементу, вы можете просто кэшировать его и обновлять кеш при вставке, если найден новый минимальный элемент.

Есть много видов структур данных кучи, которые вы можете попробовать (наклонные кучи, расширенные кучи, парные кучи, биномиальные кучи, косые биномиальные кучи, варианты вышеперечисленного с начальной загрузкой). Подробный анализ их дизайна, реализации и реальной производительности см. В статье Структуры данных: куча в The F # .NET Journal .

Функциональные структуры данных для очередей с приоритетом обсуждаются в выпуске 16 из The Monad.Reader , что интересно.

Он включает в себя описание кучи спаривания, которое быстро и очень легко реализовать.