Co dělá heap push a jak přidává prvek do haldy?

Heap push — je operace přidání nového prvku do datové struktury „halda“ (heap), která zachovává vlastnosti haldy (například minimální nebo maximální).

Jak probíhá přidání:

1. Nový prvek je umístěn na konec pole představujícího haldu.
2. Poté se provádí operace "sifování nahoru" (sift-up nebo bubble-up): prvek je porovnán s rodičem, a pokud je porušena vlastnost haldy (například v min-hladi, pokud je prvek menší než rodič), prvky se vymění.
3. Tento proces se opakuje, dokud prvek není na správné pozici, čímž se obnoví vlastnosti haldy.

Tímto způsobem zajišťuje heap push přidání prvku při zachování uspořádání haldy, což umožňuje efektivní extrakci minimálního nebo maximálního prvku.

Příklad v Pythonu s modulem heapq:

import heapq

heap = [1, 3, 5, 7]
heapq.heapify(heap)  # Přemění seznam na haldu

heapq.heappush(heap, 2)  # Přidá prvek 2
print(heap)  # Hald s zachovaným pořadím

Výsledkem bude, že prvek 2 bude přidán a "sifován" nahoru, aby se zachovaly vlastnosti min-haldy.