O (k (logk + deg (H)) алгоритм времени, чтобы найти k-й наименьший элемент в биномиальном дереве

Question

Учитывая биномиальное дерево (не кучу), когда root имеет ранг

deg(H) -> means number of nodes = 2^(deg(H)).

Найти O(k(logk+deg(H)) алгоритм времени, чтобы вернуть отсортированный массив из k наименьших элементов, без уничтожения исходного дерева .

O(klogk) известно, но я не могу выполнить удаление min для исходного дерева.

Также, если k < Deg(H), как могу ли я гарантировать logk?

Например root с 8 детьми и k = 3. Если я создам новую кучу и скопирую туда 8 узлов, удаление элемента будет logDeg(H), а не logk.

Answer 1

Учтите следующее: Создайте новое биномиальное дерево. Для K уровней дерева вставьте все узлы K-го уровня в биномиальное дерево, а затем выполните delete-min ровно k раз. Для вставки потребуется O (1 ) для каждой вставки, и на каждом уровне вы будете делать вставки Deg (H) в худшем случае. Поэтому для создания нового дерева потребуется O (kdeg (H)) . Каждая минута удаления занимает O (logk) и выполняется k раз, поэтому потребуется O (klogk) . Объединение двух приведет к желаемой сложности.