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

Question

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

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

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

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

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

Answer 1

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

Answer 2

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

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

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

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

---

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

---

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

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

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

Answer 3

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

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

---

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

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

Answer 4

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

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