Если мы упорядочим массив в порядке возрастания, то получим Binary Heap. Есть ли недостаток этого преимущества. Если да, то что будет причиной этого?
Msgstr «Расположив массив в порядке возрастания, мы получим Бинарную кучу». Это правильно.
Теперь это зависит от того, какой алгоритм вы используете для сортировки массива в порядке возрастания. Лучший алгоритм сортировки выполняет со сложностью O(NLogN)
,
Пока алгоритм Build_Heap
просто создать двоичную кучу имеет сложность O(N)
,
Если и до тех пор, пока вы не используете метод сортировки, не основанный на сравнении, как Counting Sort
Ваша сложность для создания двоичной кучи будет как минимум O(NLogN)
и самое большее O(N^2)
,
Поэтому традиционный способ создания двоичной кучи выгоден.
Хотя Counting Sort
возьму O(N)
время, но это потребует дополнительного пространства O(N)
в то время как традиционный Build_Heap
будет создавать двоичную кучу на месте.
Других решений пока нет …