Проблема с кучей Фибоначчи

Question

Я работаю над реализацией Fibonacci Heap в Java уже около недели. Это реализация, основанная на книге CLRS.

Я хотел посмотреть, получу ли я какое-либо повышение производительности, используя его в стороннем проекте, над которым я работаю, по сравнению с PriorityQueue по умолчанию в Java. [Реализация по умолчанию в Java основана на массивах, поэтому гораздо более локальна. Он все еще может превзойти F-Heap, несмотря на более высокие оценки сложности].

Кажется, моя проблема связана с частью кучи консолидации после удаления элемента min. Я продолжаю получать массив исключений исключений. В частности, в цикле while, когда объединяются все узлы одинаковой степени. Превышение границ, установленных функцией D ().

Так что либо моя функция D () неверна, что, я думаю, не так, либо что-то еще происходит. Скорее всего, связанный побочный эффект.

Код находится здесь . Я пытался отладить это в течение недели с теперь удачей. Я что-то упускаю из виду?

Answer 1

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

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