Когда использовать биномиальную кучу?

Question

Binomial Heap имеет совершенно особый дизайн. Лично я не думаю, что этот дизайн интуитивно понятен.

Несмотря на то, что сообщения, такие как What is the difference between binary heaps and binomial heaps?, говорят о diff и его специальности, я все еще задаюсь вопросом, когда я должен его использовать.

В http://en.wikipedia.org/wiki/Binomial_heap, он говорит

Благодаря своей уникальной структуре, биномиальное дерево порядка к можно , построенный из двух деревьев порядка к-1 тривиальным путем присоединения одного из их в качестве крайнего левого ребенка корень другого. Эта особенность является центральной для операции слияния биномиальной кучи, которая является ее основным достоинством перед другими обычными кучами.

Я предполагаю, что преимуществом Binomial Heap является его слияние. Однако Leftist heap также имеет слияние O (logN) и намного проще, почему мы все еще используем Binomial Heap? Когда следует использовать биномиальную кучу?

---

редактировать

Один из фактического вопроса я хочу спросить здесь Что именно преимущество биномиальной кучи?

Answer 1

В статье для Leftist tree говорит:

При установке нового узла в дерево, новое дерево один-узел создается и объединены в существующее дерево. Чтобы удалить минимальный элемент, мы удаляем корень, а затем левые и правые поддеревья объединяются. Обе эти операции занимают время O (log n). Для вложений это медленнее, чем биномиальные кучи, которые поддерживают вставку в амортизированном постоянном времени, O (1) и O (log n) в худшем случае.

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

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

Answer 2

Нет ответа на ваш вопрос.

Постоянным фактором в отношении времени выполнения для размера данных для алгоритмов на уровне библиотеки, как это часто, является выбор. Например, если операция O (1) в 20 раз медленнее, чем O (log n), когда n = 1, вам лучше выбрать алгоритм O (log n) для n < 1,000,000.

Вывод состоит в том, что асимптотические временные рамки являются лишь руководством. Вы должны использовать Binomial, а не левые кучи, если

1. Разница в приложении. (Если он не использует самую дешевую надежную реализацию под рукой, независимо от алгоритма.)
2. Тесты BH лучше, чем LH в конкретном приложении, которое вы строите.

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

Это хорошо. Это то, как развивается информатика. Подход может окупиться большим в других условиях, даже если нет большой победы над проблемой.

Примером этого является список пропусков, которые были разработаны в 1989 году для решения одной и той же проблемы с почти той же эффективностью, что и сбалансированные деревья двоичного поиска, которые были известны в 1962 году или ранее. Зачем беспокоиться? Потому что мы можем.

Answer 3

Биномиальные кучи поддерживают операцию слияния (деструктивно объединить две кучи) в логарифмическом времени, тогда как линейное время занимает двоичная куча.

Answer 4

Binary Heap < Бином Heap < Фибоначчи Heap

Это только по отношению к производительности. От Wiki,

+------------+---------------+----------+-----------+ 
| Operation | Binary  | Binomial | Fibonacci | 
+------------+---------------+----------+-----------+ 
| Find-min | Θ(1)   | Θ(1)  | Θ(1)  | 
| delete-min | Θ(log n)  | Θ(log n) | O(log n) | 
| insert  | Θ(log n)  | Θ(1)  | Θ(1)  | 
| dec-key | Θ(log n)  | Θ(log n) | Θ(1)  | 
| merge  | Θ(m log(n+m)) | O(log n) | Θ(1)  | 
+------------+---------------+----------+-----------+