двоичная куча против биномиальной кучи против кучи Фибоначчи, относительно производительности для очереди с приоритетом

Не мог бы кто-нибудь объяснить мне, как мне решить, использовать ли ту или иную реализацию кучи, среди тех, которые упомянуты в заголовке?

Я хотел бы получить ответ, который помог бы мне выбрать реализацию с точки зрения производительности структуры в соответствии с проблемой. Прямо сейчас я занимаюсь приоритетной очередью, но я хотел бы знать не только наиболее подходящую реализацию для этого случая, но и основы, которые позволяют мне выбирать реализацию в любой другой ситуации ...

Также следует учитывать, что на этот раз я использую haskell, поэтому, если вы знаете какой-либо трюк или что-то, что могло бы улучшить реализацию этого языка, сообщите мне! но, как и раньше, приветствуются и комментарии об использовании других языков!

Спасибо! и извините, если вопрос слишком простой, но я вообще не знаком с кучей. Это первый раз, когда я сталкиваюсь с задачей реализовать один ...

еще раз спасибо!


performance haskell fibonacci binary-heap binomial-heap
person Throoze    schedule 02.12.2011    source источник
comment
Эх, если вы впервые реализуете кучу, просто сначала напишите версию, используя двоичную кучу. Просто сделайте его достаточно абстрактным, чтобы вы могли заменить его чем-нибудь другим, если вам действительно понадобится. Биномиальные кучи и кучи Фибоначчи намного сложнее двоичных, и, вероятно, с ними не стоит бороться (если, конечно, вы не хотите просто узнать о них).   -  person Tikhon Jelvis    schedule 02.12.2011
comment
Мне больше всего нравится Леонардо. Они появляются в Dijkstras Smoothsort.   -  person fuz    schedule 02.12.2011
comment
Внедрите их все и сравните их с вашим приложением.   -  person augustss    schedule 02.12.2011
comment
@TikhonJelvis: ну, я бы хотел узнать обо всех из них. Я задал этот вопрос, потому что мне нужно выбрать один для этого проекта (это для колледжа), но я хотел бы знать, какой из них лучший, и уловки реализации. В этом проекте меня просят иметь самое большее время O (log n) для операций вставки и extractMin. Я знаю, что на этот раз есть и биномиальные, и фибоначчи, но я хотел бы знать, как выбрать. Я не знаю, быстрее или медленнее двоичный файл, но это мой вопрос! какой я выберу? и почему? Благодарность!   -  person Throoze    schedule 03.12.2011
comment
Прочтите эту статью. В нем перечислены разные времена. Вы обнаружите, что двоичная куча также удовлетворяет вашим ограничениям. Поскольку двоичная куча намного проще и элегантнее, я бы предложил использовать ее, даже если другие могут иметь лучшую производительность.   -  person Tikhon Jelvis    schedule 03.12.2011
comment
Определенно сначала выберите более простой. В разработке программного обеспечения всегда считается правилом предположить, что более простое решение будет достаточно хорошим, а затем оптимизировать его после проведения измерений. Попытки угадать без доказательств просто заставят вас потратить впустую усилия.   -  person Paul Johnson    schedule 03.12.2011
comment
Возможно, вы захотите увидеть какова-разница-между-двоичными-кучей и-биномиальными-кучами?, когда использовать-биномиальную-кучу?, что- is-the-intuition-behind-the-fibonacci-heap-data-structure, реальных-приложений-двоичных- heaps-and-fibonacci-heaps, эффективных-кучи-в-чисто-функциональных-языках   -  person nawfal    schedule 15.06.2014
comment
возможный дубликат эффективных куч на чисто функциональных языках   -  person Ciro Santilli 新疆再教育营六四事件ۍ    schedule 20.06.2015

Ответы (4)


arrow_upward
4
arrow_downward

Вы можете найти третью статью в http://themonadreader.files.wordpress.com/2010/05/issue16.pdf актуально.

person Louis Wasserman    schedule 03.12.2011
comment
В третьей статье, на странице 45, когда они определяют data Succ rk a = BinomTree rk a ? rk a, перед вторым rk a есть забавный символ, например, сложенный треугольник (вместо написанного мной символа '?') ... Я не очень привык к синтаксису haskell, не могли бы вы объяснить мне, что означает этот символ ?? Благодарность! - person Throoze; 04.12.2011
comment
@Throoze: странный треугольник - это просто инфиксный конструктор данных для типа Succ. Вы можете прочитать эту строку как: data Succ rk a = Succ (BinomTree rk a) (rk a) - person opqdonut; 04.12.2011
comment
Это просто символ, делающий бумагу более читаемой. При написании самой программы я обычно пишу конструктор инфиксов: ‹: объяснение opqdonut тоже работает. - person Louis Wasserman; 05.12.2011
comment
(Кроме того, полное раскрытие: я являюсь автором этой статьи.) - person Louis Wasserman; 05.12.2011

arrow_upward
3
arrow_downward

Во-первых, вы не будете реализовывать стандартную кучу в Haskell. Вместо этого вы будете реализовывать постоянную и функциональную кучу. Иногда функциональные версии классических структур данных столь же эффективны, как и исходные (например, простые двоичные деревья), но иногда нет (например, простые очереди). В последнем случае вам понадобится специализированная функциональная структура данных.

Если вы не знакомы с функциональными структурами данных, я предлагаю начать с замечательного книга или диссертация (интересующие главы: на минимум 6.2.2, 7.2.2).

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

PS. Отличный ответ cstheory.se

person opqdonut    schedule 04.12.2011

arrow_upward
2
arrow_downward

У них разная временная сложность для разных операций с приоритетной очередью. Вот вам наглядная таблица

╔══════════════╦═══════════════════════╦════════════════════════╦══════════════════════════════╗
║  Operation   ║       Binary          ║      Binomial          ║       Fibonacci              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║   insert     ║      O(logN)          ║      O(logN)           ║         O(1)                 ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║  find Min    ║       O(1)            ║      O(logN)           ║         O(1)                 ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║   Revmove    ║       O(logN)         ║      O(logN)           ║        O(logN)               ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║ Decrease Key ║       O(logN)         ║      O(logN)           ║        O(1)                  ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║    Union     ║         O(N)          ║      O(logN)           ║        O(1)                  ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║ ■ Min element is root ║order k binomial tree Bk║ ■ Set of heap-ordered trees. ║
║              ║ ■ Heap height = logN  ║ ■ Number of nodes = 2k.║ ■ Maintain pointer to min.   ║
║              ║                       ║ ■ Height = k.          ║   (keeps find min/max O(1))  ║                        
║              ║                       ║ ■ Degree of root = k.  ║ ■ Set of marked nodes.       ║
║  Useful      ║                       ║ ■ Deleting root yields ║   (keep the heaps flat)      ║
║  Properties  ║                       ║   binomial trees       ║                              ║
║              ║                       ║   Bk-1, … , B0.        ║                              ║
║              ║                       ║   (see graph below)    ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║             
╚══════════════╩═══════════════════════╩════════════════════════╩══════════════════════════════╝

Я взял это изображение из слайдов лекций в Принстоне

Двоичная куча: введите описание изображения здесь

Биномиальная куча:

k бономиальных деревьев

Куча Фибоначчи:

введите здесь описание изображения

Примечание: биномиальная куча и куча Фибоначчи выглядят знакомо, но несколько отличаются:

  • Биномиальная куча: стремительно объединяйте деревья после каждой вставки.
  • Куча Фибоначчи: лениво откладывать консолидацию до следующего delete-min.
person OLIVER.KOO    schedule 02.01.2018

arrow_upward
1
arrow_downward

Некоторые ссылки на функциональную биномиальную кучу, кучу Фибоначчи и кучу сопряжения: https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf

Если действительно проблема в производительности, я предлагаю использовать кучу сопряжения. Единственный риск заключается в том, что его производительность до сих пор остается лишь предположением. Но эксперименты показывают, что производительность неплохая.

person Larry LIU Xinyu    schedule 17.08.2012