двоичная куча против биномиальной кучи против кучи Фибоначчи, относительно производительности для очереди с приоритетом
https://stackoverflow.com/questions/8353038
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Не мог бы кто-нибудь объяснить мне, как мне решить, использовать ли ту или иную реализацию кучи, среди тех, которые упомянуты в заголовке?
Я хотел бы получить ответ, который поможет мне выбрать реализацию с учетом производительности структуры в соответствии с проблемой.Прямо сейчас я занимаюсь приоритетной очередью, но я хотел бы знать не только наиболее подходящую реализацию для этого случая, но и основы, которые позволяют мне выбирать реализацию в любой другой ситуации ...
Также следует учитывать, что на этот раз я использую haskell, поэтому, если вы знаете какой-либо трюк или что-то, что могло бы улучшить реализацию этого языка, сообщите мне!но, как и раньше, приветствуются и комментарии об использовании других языков!
Спасибо!и извините, если вопрос слишком простой, но я вообще не знаком с кучей.Я впервые сталкиваюсь с задачей реализовать один ...
еще раз спасибо!
Решение
Вы можете найти третью статью в http://themonadreader.files.wordpress.com / 2010/05 / issue16.pdf актуально.
Другие советы
Прежде всего, вы не будете реализовывать стандартную кучу в Haskell. Вместо этого вы будете реализовывать постоянную и функциональную кучу. Иногда функциональные версии классических структур данных столь же эффективны, как и исходные (например, простые двоичные деревья), но иногда нет (например, простые очереди). В последнем случае вам потребуется специализированная функциональная структура данных.
Если вы не знакомы с функциональными структурами данных, я предлагаю начать с замечательного книга или диссертация (главы проценты: не менее 6.2.2, 7.2.2).
Если все это вышло вам в голову, я предлагаю начать с реализации простой связанной двоичной кучи. (Создание эффективной двоичной кучи на основе массивов в Haskell немного утомительно.) Как только это будет сделано, вы можете попробовать свои силы в реализации биномиальной кучи с помощью псевдокода Окасаки или даже начать с нуля.
У них разная временная сложность для разных операций с приоритетной очередью. Вот вам наглядная таблица
родовое словоЯ получил это изображение из слайдов лекций Принстона
Биномиальная куча:
Куча Фибоначчи:
Примечание. Биномиальная куча и куча Фибоначчи выглядят знакомо, но несколько отличаются:
- Биномиальная куча: объединяйте деревья после каждой вставки.
- Куча Фибоначчи: отложите консолидацию до следующей минуты удаления.
Некоторые ссылки на функциональную биномиальную кучу, кучу Фибоначчи и кучу сопряжения: https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf
Если действительно проблема в производительности, я предлагаю использовать кучу сопряжения.Единственный риск заключается в том, что его производительность до сих пор остается предположением.Но эксперименты показывают, что производительность неплохая.
