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

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

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

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

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

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

Ответ 1

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

Ответ 2

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

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

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

PS. Этот ответ cstheory.se велик

Ответ 3

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

╔══════════════╦═══════════════════════╦════════════════════════╦══════════════════════════════╗
║  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)    ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║             
╚══════════════╩═══════════════════════╩════════════════════════╩══════════════════════════════╝

Я получил это изображение из слайды лекций Princeton

Двоичная куча:

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

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

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

Биномиальная куча: жадно объединяйте деревья после каждой вставки.
Куча Фибоначчи: лениво отложить консолидацию до следующего удаления-мин.

Ответ 4

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

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