Co robi heap push i jak dodaje element do kopca?

Heap push — to operacja dodania nowego elementu do struktury danych „kupa” (heap), która utrzymuje właściwości kopca (np. minimalny lub maksymalny).

Jak przebiega dodanie:

1. Nowy element jest umieszczany na końcu tablicy reprezentującej kopiec.
2. Następnie wykonywana jest operacja "siania w górę" (sift-up lub bubble-up): element jest porównywany z rodzicem, a jeśli narusza to właściwości kopca (np. w kopcu minimalnym, jeśli element jest mniejszy od rodzica), elementy zamieniają się miejscami.
3. Proces ten powtarza się, aż element znajdzie się na właściwej pozycji, przywracając właściwości kopca.

W ten sposób, heap push zapewnia dodanie elementu z zachowaniem uporządkowania kopca, co umożliwia efektywne wydobycie elementu minimalnego lub maksymalnego.

Przykład w Pythonie z użyciem modułu heapq:

import heapq

heap = [1, 3, 5, 7]
heapq.heapify(heap)  # Zamienia listę na kopiec

heapq.heappush(heap, 2)  # Dodaje element 2
print(heap)  # Kopiec z zachowaną kolejnością

W rezultacie, element 2 zostanie dodany i "sianowany" w górę, aby zachować właściwości kopca minimalnego.