Что делает heap push и как он добавляет элемент в кучу?

Heap push — это операция добавления нового элемента в структуру данных «куча» (heap), которая поддерживает свойства кучи (например, минимальную или максимальную).

Как происходит добавление:

1. Новый элемент помещается в конец массива, представляющего кучу.
2. Затем выполняется операция "просеивания вверх" (sift-up или bubble-up): элемент сравнивается с родительским, и если нарушается свойство кучи (например, в мин-куче элемент меньше родителя), элементы меняются местами.
3. Этот процесс повторяется, пока элемент не окажется на правильной позиции, восстанавливая свойства кучи.

Таким образом, heap push обеспечивает добавление элемента с сохранением упорядоченности кучи, что позволяет эффективно извлекать минимальный или максимальный элемент.

Пример на Python с использованием модуля heapq:

import heapq

heap = [1, 3, 5, 7]
heapq.heapify(heap)  # Превращаем список в кучу

heapq.heappush(heap, 2)  # Добавляем элемент 2
print(heap)  # Куча с сохранением порядка

В результате элемент 2 будет добавлен и "просеян" вверх, чтобы сохранить свойства мин-кучи.