Псевдокод для очереди Бродал

12

Я пытаюсь найти больше ресурсов о куче Бродал . Все, что я нашел, это реализация на хаскелле кучи Бродала-Окасаки , но я думаю , что это косые кучи , верно? Кроме того, я неграмотен в Хаскеле, так что это не сильно помогает. Кто-нибудь имеет (или знает) реализацию очереди Brodal в псевдокоде, C, C ++, Python?

Также, пожалуйста, исправьте, если мои предположения выше неверны.

research data-structures Kimvais
источник
3
Вы ищете конкретную реализацию очереди Brodal или ищете эффективную реализацию очереди с приоритетами? Бродал упомянул в заключении своей статьи, что они не практичны без дальнейших исследований в этой области. Его статья была процитирована, может быть, что-то полезное? В CLR Введение в алгоритмы есть раздел о приоритетных очередях, но он ссылается на более раннюю работу в приоритетных очередях.
Джей Элстон,
2
Исходная очередь Brodal использует деструктивное присваивание, поэтому версия на Haskell должна иметь некоторые модификации.
Фред Фу

Ответы:

2

Реализация Haskell основана на функциональной куче Бродала-Окасаки, и вы правы, это разновидность косых куч. Статья написана очень четко, поэтому это был бы хороший ресурс.

Что касается реализации, то есть также реализация в Scala как часть библиотеки scalaz.

maayank
источник
1

Это частичный ответ, так как я еще не понял, как перевести код во что-то, что не является Haskell. Причина, по которой я могу сказать, что им приходится использовать Haskell, заключается в том, что Haskell ленив. Куча Бродал-Окасаки должна быть ленивой из бумаги. Поэтому вам нужен способ предоставления этой функциональности другому языку вместе с любыми другими требованиями (такими как чисто функциональные структуры данных), которые могут понадобиться в куче BO.

Мировой инженер
источник