Какая разница в heapify и heappush? что лучше?

Question

heapify и heapush и помещают минимальный элемент сверху, а самые низкие элементы находятся в правильном месте. Я не понимаю, в чем разница и разница использования

import heapq
H = [21,1,45,78,3,5]
# Covert to a heap

# Add element
heapq.heappush(H,-100)
heapq.heappush(H,-98)
heapq.heappush(H,-1)
print(H)
heapq.heapify(H)

print(H)


# output: [-100, -98, 21, -1, 3, 5, 45, 78, 1]
# [-100, -98, 5, -1, 3, 21, 45, 78, 1]

Answer 1

Есть несколько различий между heappush и heapify.

1. heappush предполагает, что массив (H в вашем случае) уже является кучей. heapify нет - H просто должен быть списком. Обратите внимание, что в вашем примере ваша структура данных H не является кучей, прежде чем вы выполните три команды heappush. (Например, H начинается как [21,1,45,78,3,5], но первый элемент 21 больше, чем второй элемент 1, что нарушает определение кучи.) В результате, H не является кучей после команд heappush тоже. (H становится [-100, -98, 21, -1, 3, 5, 45, 78, 1], но 3-й элемент 21 больше, чем 6-й элемент 5, что также нарушает определение кучи.) После элементов heapify, 5 и 21 поменялись местами, и H будет правильной кучей.
2. heappush добавляет новое значение в кучу. heapify не добавляет значение - оно переупорядочивает значения в списке.
3. Вы можете создать кучу, создав пустую кучу, затем вызывая heappush для каждого элемента, который вы хотите добавить, или вы можете составить список элементов в любом порядке, а затем вызвать heapify в списке. Метод heappush будет иметь временную сложность O (n * log (n)), где n - конечный размер кучи, в то время как метод heapify будет иметь сложность O (n), которая значительно ниже. Например, если вы создаете кучу из одного миллиона элементов, метод heappush может использовать до порядка 20,000,000 операций, в то время как метод heapify использует только самое большее из порядка 1,000,000 операций. , Это фактор разницы 20. Конечно, операции не совсем одинаковы, а фактические числа немного отличаются, поэтому фактический коэффициент будет другим, но heapify почти наверняка будет быстрее.
4. Для построения кучи heappush требуется множество отдельных операторов или какой-то цикл для добавления элементов. Метод heapify просто требует существования списка. Поэтому метод heapify, скорее всего, будет использовать меньше строк кода и меньшую сложность кода. (Добавление цикла for в ваш код добавляет еще один уровень сложности, который может привести к большему количеству ошибок.)

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