Speical minHeap - это minHeap, который каждый уровень сортируется слева направо. Как я могу напечатать все элементы n по заказу в O(n) в наихудшем случае?special minHeap, как печатать все n элементов в O (n)?
MinHeap реализуется двоичной кучей, в которой дерево является полным двоичным деревом (см. Рисунок).
вот пример особого minHeap:
Так что результат должен быть: [1,3,4,5,8,10,17,18,20,22,25,30]
Вопрос от домашней работы.
Если n является параметром, независимым от размера кучи, то при стандартной модели на основе сравнения это невозможно. Вам понадобятся дополнительные ограничения, такие как более предыдущий порядок, чем вы упомянули, или все элементы кучи являются целыми числами при достаточно низкой границе.
Предположим, что у вас есть куча высоты k, где корень и его цепь левых детей имеют значения 1, 2, 3, ... k. Мы можем назначить значения> k правым дочерним элементам k-1 этих узлов в любом порядке, не нарушая условие «специального minheap», а затем присваиваем значения, превышающие значения для заполнения остальной части кучи. Печать верхних значений 2k-1 в этой куче требует сортировки значений k-1, которые могут быть в любом порядке, что невозможно сделать путем сравнений менее чем за O(k*log(k)) времени.
Если n должен быть размер кучи, это просто. Инвариант кучи не нужен; имеет значение только то, что слои отсортированы. Объединение первого и второго слоев, а затем объединение каждого последующего слоя в уже сведенные результаты займет O (n). К-мерное слияние объединяет 2^k-1 уже объединенных элементов с < = 2^k элементов из следующего слоя, принимая время O (2^k). O (log (n)) сливается, и суммирование O (2^k) от k = 1 до k = log (n) дает O (n).
Это был аргумент, который я имел в виду, но иногда определение 'minHeap' требует, чтобы оно было полным двоичным деревом (как в примере). Поэтому я все еще не уверен. – WhatsUp
@WhatsUp: Этот аргумент использует полное двоичное дерево, поэтому я не уверен, какую проблему вы видите. – user2357112
Полная куча будет иметь около '2^k' узлов, поэтому проблема требует распечатки всех из них в' O (2^k) 'времени. Это все еще немного отличается от печати первых значений «2k - 1» в «O (k)» времени. – WhatsUp
Каждый уровень кучи находится в порядке возрастания. Есть log (n) уровней.
Мы можем выполнить слияние уровней, которое равно O (n log k). k в этом случае - количество уровней или log (n), поэтому мы знаем, что это возможно сделать в O (n * log (log n)).
Уровни имеют в них 1, 2, 4, 8, 16 и т. Д. Узлы. Первая операция слияния удаляет первый уровень, поэтому количество элементов в нашей куче слияния становится k-1. В худшем случае после удаления половины узлов куча слияния равна k-2 и т. Д.
У меня нет математики под рукой, но я подозреваю, что решение включает в себя показ того, что расширение серии (т.е. отслеживание размера кучи слияния и умножение на количество узлов, проходящих через каждую кучу размера) сокращается до 2, как указано в комментариях.
Правильный ответ, думаю. Сливаясь сверху вниз, на самом деле достигается сложность «O (n)», поскольку размеры уровней образуют геометрическую серию отношения «2». – WhatsUp
Это O (n). Математика относительно проста; Я сделал это в своем ответе. – user2357112
Возможно, вы захотите уточнить, какую структуру данных вы используете для хранения кучи. – ilim
Очевидно, что не ** MergeSort **, потому что ** MergeSort ** принимает 'O (nlogn)' –
Это упражнение/домашнее задание? – WhatsUp