Блог

Какая последовательность операций даст наихудший случай для куч фибоначчи? Где у каждого узла есть только один дочерний элемент, за исключением последнего узла?

Например:

 5
|
6
|
7
|
8
  

Я думаю, что ответ jpalecek не создает запрошенное дерево. Попробуйте это здесь:

http://www.cse.yorku.ca / ~aaw/Jason/FibonacciHeapAnimation.html

Кроме того, вы можете достичь того же результата, просто вставив любое количество элементов, а затем извлечь минимум один раз. В любом случае, это не запрос.

Чтобы получить желаемую форму, сделайте это:

• вставьте любое количество элементов — скажем, от 1 до 10.
• извлеките min (теперь у вас есть единственное дерево)
• уменьшите все дочерние элементы до -inf , кроме самого левого, начиная с самого глубокого и слева направо (см. демонстрацию ниже).
• после каждого уменьшения удаляйте минимальное
• повторите шаг 3

пример:

• вставить с 1 по 10:

• извлеките минимум:

• уменьшить 7 до 0 :

• извлеките минимум:

• уменьшите 5 до 0 , извлеките min , уменьшите 4 до 0 , извлеките min, уменьшите 3 до 0 , извлеките min, уменьшите 10 до 0 , извлеките min:

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

Я забыл, что есть delete операция, которая делает decrease then extract min , поэтому вы можете использовать ее вместо уменьшения, а затем извлечения min, которое я делал выше.

И обратите внимание, что теперь, когда у вас есть дерево «единого пути», вы можете легко продолжать увеличивать его с помощью этой последовательности из O (1) операций:

• вставьте 3 элемента, меньших минимального
• извлеките минимум
• удалите нового правого дочернего элемента

демонстрация (продолжение последнего шага из примера):

• вставить 1 , 0 , -1 :

• извлеките минимум:

• удалить нового правого дочернего элемента ( 1 ):

все изображения созданы этим веб-сайтом

На самом деле это наилучший вариант (как вы можете видеть, extract-min всегда прост, поскольку у нас упорядочены элементы). Вы должны получить его, вставив последовательность элементов с обратной сортировкой (то есть минимальный элемент будет последним) таким образом:

1. вставить два элемента
2. извлечение-минимум
3. повторить