Ответ 1
Вы можете найти третью статью в http://themonadreader.files.wordpress.com/2010/05/issue16.pdf.
Бинарная куча против биномиальной кучи против кубика фибоначчи, касающаяся производительности для очереди приоритетов
Может кто-нибудь, пожалуйста, объясните мне, как мне решить, следует ли использовать ту или иную реализацию кучи, среди тех, которые указаны в названии?
Я хотел бы получить ответ, чтобы помочь мне выбрать вариант реализации производительности в соответствии с этой проблемой. Прямо сейчас, я делаю очередь приоритетов, но я хотел бы знать не только наиболее подходящую реализацию для этого случая, но и основы, которые позволяют мне выбирать реализацию в любой другой ситуации...
Другое дело, что я использую haskell на этот раз, поэтому, если вы знаете какой-либо трюк или что-то, что улучшит реализацию с помощью этого языка, пожалуйста, дайте мне знать! но, как и раньше, комментарии об использовании других языков тоже приветствуются!
Спасибо! и извините, если вопрос слишком прост, но я вообще не знаком с кучами. Это первый раз, когда я сталкиваюсь с задачей реализации одного...
Еще раз спасибо!
Ответы
Ответ 2
Прежде всего, вы не будете внедрять стандартную кучу в Haskell. Вместо этого вы будете использовать постоянную и функциональную кучу. Иногда функциональные версии классических структур данных являются такими же эффективными, как и оригинальные (например, простые двоичные деревья), но иногда нет (например, простые очереди). В последнем случае вам понадобится специализированная структура функциональных данных.
Если вы не знакомы с функциональными структурами данных, я предлагаю начать с Okasaki большой книга или тезис (интересующие главы: не менее 6.2.2, 7.2.2).
Если все это пошло вам на голову, я предлагаю начать с реализации простой связанной двоичной кучи. (Создание эффективной массивной двоичной кучи в Haskell немного утомительно.) Как только это будет сделано, вы можете попробовать свои силы при реализации биномиальной кучи, используя псевдокод Okasaki или даже начать с нуля.
Ответ 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
Если производительность действительно является проблемой, я предлагаю использовать кучу спаривания. Единственный риск состоит в том, что его производительность до сих пор остается догадкой. Но эксперименты показывают, что производительность неплохая.