Формирование двоичных кучи с использованием ярлыков массивов

Если мы упорядочим массив в порядке возрастания, то получим Binary Heap. Есть ли недостаток этого преимущества. Если да, то что будет причиной этого?

0

Решение

Msgstr «Расположив массив в порядке возрастания, мы получим Бинарную кучу». Это правильно.
Теперь это зависит от того, какой алгоритм вы используете для сортировки массива в порядке возрастания. Лучший алгоритм сортировки выполняет со сложностью O(NLogN),

Пока алгоритм Build_Heap просто создать двоичную кучу имеет сложность O(N),

Если и до тех пор, пока вы не используете метод сортировки, не основанный на сравнении, как Counting Sort Ваша сложность для создания двоичной кучи будет как минимум O(NLogN) и самое большее O(N^2),

Поэтому традиционный способ создания двоичной кучи выгоден.

Хотя Counting Sort возьму O(N) время, но это потребует дополнительного пространства O(N)в то время как традиционный Build_Heap будет создавать двоичную кучу на месте.

0

Другие решения

Других решений пока нет …