Формирование бинарных куч с помощью ярлыка массивов

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

Knowledge Reg, в 06:17 (источник)

1 ответ

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

    В то время как алгоритм Build_Heapдля простого создания бинарной кучи имеет сложность O(N).

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

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

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