Распечатать дерево в отсортированном порядке, используя свойства кучи (Cormen)

Question

Я обновляю теорию алгоритмов (из Cormen).
В главе для двоичных попыток есть упражнение, которое спрашивает:

Можно ли использовать свойство min-heap для распечаткиключи дерева n-узлов в отсортированном порядке за O (n) раз?Покажите, как, или объясните, почему нет.

Я думал, что да, это возможно.
В минимальной куче элемент в узле меньше, чем оба его потомка.
Так что коренькуча всегда является меньшим элементом из всех n элементов, а левый дочерний элемент корня меньше, чем все элементы в левом поддереве, а правый дочерний элемент корня меньше всех элементов в правом поддереве и т. д.

Поэтому, если мы продолжаем извлекать корень, распечатываем его, а затем обновляем корень с меньшим из его дочерних элементов, мы сохраняем свойство min-heap и печатаем в отсортированном порядке.(Я имею в виду минимальную кучу, которая не основана на массиве).

Так что это можно сделать за O (n) раз, так как для обновления корня мы просто сравниваем 2 дочерних элемента и обновляем указатель корня, чтобы он был меньшим из 2.

Но япроверено здесь в решении:
Решения для дополнения Cormen

И 1) это говорит о максимальных кучах 2) оно говорит, что не может быть сделано за O (n) время:

В куче ключом узла являются оба его дочерних ключа.В бинарном дереве поиска ключом узла является ключ его левого потомка, но ключ его правого потомка.Свойство heap, в отличие от свойства binary-searth-tree, не помогает печатать узлы в отсортированном порядке, поскольку не сообщает, какое поддерево узла содержит элемент для печати перед этим узлом.В куче самый большой элемент, меньший, чем узел, может находиться в любом поддереве.Обратите внимание, что если бы свойство heap могло использоваться для печати ключей в отсортированном порядке за O (n) время, у нас был бы алгоритм O (n) времени для сортировки, потому что построение кучи занимает только O (n) время.Но мы знаем (Глава 8), что сортировка сравнения должна занимать (n lg n) время.

С моей точки зрения, я могу понять, что с помощью max-heap невозможно распечататьих в O (n).
Но разве невозможно сделать это, используя свойство min-heap по объяснению, которое я объяснил?
Кроме того, почему решение игнорирует min-heap.Это опечатка или ошибка?

Я что-то здесь неправильно понимаю?

Answer 1

Во-первых, пропуск min-heaps в обсуждении, вероятно, не является опечаткой, не имеет значения, говорим ли мы о min-heap или max-heap (компаратор просто перевернут).

Проблема только с извлечением корня и последующей заменой меньшим из двух его дочерних элементов заключается в том, что левый дочерний элемент не обязательно будет меньше всех узлов в правом поддереве (и наоборот).Рассмотрим следующую кучу

        1
       / \
      4   6
     /\   /\
    5  8 9  7

После печати 1 вам нужно заново переучить, что означает, что вы извлекаете 1 и заменяете его последним элементом в последней строке, в данном случае 7.Затем вы переключаетесь на столько времени, сколько вам нужно, чтобы вернуть кучу в правильное состояние

take away root and last node to root
        7
       / \
      4   6
     /\   /
    5  8 9

swap
        4
       / \
      7   6
     /\   /
    5  8 9

swap
        4
       / \
      5   6
     /\   /
    7  8 9

, весь этот обмен стоит вам log n времени.

Если вы заменили корневой узелс 4 вам все равно придется пройти через левую ветвь, чтобы переучить структуру, добавив стоимость к линейной стоимости извлечения корневых узлов.Что, если куча выглядела так

        1
       / \
      4   9
     /\   /\
    5  6 11 15
   /\
  8  7

Страницы, на которых я смотрел, формируя решение

1) Википедия: двоичная куча

2) Wolfram MathWorld: куча Кучи здесь особенно полезны для понимания, почему это не линейная операция.

Answer 2

Рассмотрим представление массива min-heap. У вас есть минимум в корне. Извлеките корень и замените его последним элементом массива, то есть последним листом в самом нижнем, неполном «ряду» листьев. Выполните операцию MIN-HEAPIFY (аналогично CLRS MAX-HEAPIFY, но с обратным сравнением). Это берет O (log n) и результат - второй наименьший элемент в корне. Повторяйте, пока куча не станет пустой. Это дает отсортированную последовательность.

Сложность алгоритма, следовательно,

log (n) + log (n-1) + log (n-2) + ... + 1 <= n*log n

т.е. O (n * log n)

что и следовало ожидать, иначе мы бы получили сортировку на основе сравнения со сложностью меньше, чем O (nlogn), и это невозможно.

Answer 3

Полагаю, вы в основном думаете, что куча (учитывая минимальную кучу) имеет наименьший элемент в качестве корня.Теперь для второго наименьшего элемента у левого и правого поддерева есть свойство min heap, поэтому мы можем просто сравнить левый и правый дочерний элемент, чтобы найти второй наименьший элемент.И то же самое можно продолжить .... так его O (n)?Одна вещь, которую вы игнорируете, заключается в том, что с каждым уровнем количество сравниваемых элементов также увеличивается ... для наименьшего сравнения - 0 (корень наименьший) для второго наименьшего сравнения - 1 (либо корень левого дерева, либокорень правого дерева) Допустим, корень левого дерева меньше корневого узла правого дерева.для третьего наименьшего - 2 сравнения.(либо корень правого дерева, либо любой из двух дочерних элементов левого поддерева).Вы игнорируете эту часть сравнения для расчета асимптотической сложности времени.