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

Question

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

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

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

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

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

Answer 1

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

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