Печать k наименьших значений по порядку от малого к наибольшему в минимальной куче в O (klog k)

Question

У меня минимальная куча H с n элементами. Функция min(H,k) печатает k наименьших значений по порядку от малого к наибольшему. В конце метода H все еще содержит значения n. Меня попросили дать алгоритм min(H,k) в O(klogk) и O(k) дополнительного пространства. В решениях они делали следующее:

Мы будем использовать дополнительную минимальную кучу T без каких-либо данных. Он будет содержать копии элементов оригинальной минимальной кучи H (между значениями из H и T будет двухсторонний указатель). Все go:

• Напечатать минимальный элемент H в O(1).
• Вставить в T двух детей root из H.
• Пока мы не печатали k значений, делайте:
  • Печать минимального элемента T (давайте назовем его x).
  • Удалить x из T.
  • Вставьте в кучу T двух детей x кучи H (если существует).

Я не понимаю, почему этот алгоритм действует и что хуже, я совсем не понимаю алгоритм. Я понимаю, что мы создаем новую кучу T. Я также понимаю, почему минимальный элемент печати H равен O(1). Я не понимаю, "Вставьте в T двух детей части root из H". Вставляет ли он указатели этих детей в кучу T или только их значения? Если ответом является второй вариант, то как я знаю, чтобы следовать следующим?

Answer 1

Элементы T должны позволять вам получить элементы и позиции элементов в исходной куче. Если вы можете сделать это, то вы можете найти следующие элементы и найти значения.

Будет работать множество представлений. Например, с представлением массива min heap все, что вам нужно знать, - это смещения в массиве, с глобальными константами для длины массива и начала массива.

Ключ к пониманию того, почему это работает то, что все операции на T являются кучными операциями на куче размером O(k). Поэтому каждый из них берет O(log(k)). Необходимо O(k) операций, поэтому результат будет O(k log(k)).