Я хочу найти Максимальное количество сравнений при преобразовании min-heap в max-heap с n узлом. Я думаю, что конвертировать мини-кучу в макс-кучу с помощью O (n). это означает, что нет способа и воссоздать кучу.Min-Heap to Max-Heap, Сравнение
В качестве грубой нижней границы, заданной деревом с свойством (min- или max-) кучи, мы не имеем предварительного представления о том, как значения в листьях сравниваются друг с другом. В максимальной куче значения в листьях все могут быть меньше всех значений во внутренних узлах. Если куча имеет топологию полного бинарного дерева, то даже для нахождения минимума требуется, по крайней мере, приблизительно n/2 сравнения, где n - число узлов дерева.
какой из них? O (n + logn), O (n log n), O (log n), O (n)? – user153695
@ user153695 Достаточно сказать, что с асимптотической точки зрения наличие структуры max-heap не помогает в min-heapify (и наоборот). –
Знание значений, даже необходимых для создания мини-кучи из максимальной кучи в O (n), хотя? Если вы в порядке с двоичной кучей, то просто heapify с любым заказом вы хотите. Разумеется, для других типов куч, которые бесполезны. –
Если у вас есть мини-куча известного размера, вы можете создать двоичную максимальную кучу своих элементов, заполнив массив от начала до начала значениями, полученными путем итерационного удаления корневого узла из мини-кучи до тех пор, пока он исчерпан. В некоторых случаях это можно сделать даже на месте. Используя правило, что корневой узел является элементом 0, а дочерние узлы i - это элементы 2i и 2i + 1, условие кучи (max-) автоматически будет выполняться для кучи, представленной новым массивом.
Каждое удаление из мини-кучи размера m требует, однако, до сравнения значений log (m) элементов для восстановления состояния кучи. Я думаю, это добавляет до O (n log n) сравнения для всей работы. Я сомневаюсь, что вы можете сделать это с любой меньшей сложностью без добавления условий. В частности, если вы не выполняете фактические удаления кучи (при условии стоимости восстановления состояния кучи), то я думаю, что вы понесете сопоставимые дополнительные затраты, чтобы убедиться, что в итоге вы получите кучу.
Вы имеете в виду максимальное количество сравнения O (n log n)? – user153695
Я имею в виду, что вы можете сделать это с помощью сравнений O (n log n). Конечно, вы могли бы просто изнашивать элементы с нуля в O (n log n). Я не думаю, что есть способ сделать это с более низкой асимптотической сложностью, но я не уверен. –
О [heapifying in O (n)] (http://stackoverflow.com/questions/9755721/build-heap-complexity) для двоичных куч. –
Вы предполагаете, что вы сохраните состояние кучи для мини-кучи, пока вы ее снижаете? –
Уважаемый @JohnBollinger, infact я хочу проверить его в каждом вероятном состоянии. на мой взгляд, просто мы хотим сменить мини-кучу на максимальную кучу и вычислить максимальное количество сравнений. – user153695