Mit csinál a heap push, és hogyan ad hozzá egy elemet a kupacba?

Heap push — ez egy művelet, amely új elemet ad hozzá a „halom” (heap) adatstruktúrához, amely fenntartja a halom tulajdonságait (például minimum vagy maximum).

Hogyan történik a hozzáadás:

1. Az új elem a halomot ábrázoló tömb végére kerül.
2. Ezután végrehajtódik az "felszínelés" (sift-up vagy bubble-up) művelet: az elem összehasonlítódik a szülőjével, és ha sérül a halom tulajdonsága (például min-halomban, ha az elem kisebb, mint a szülője), az elemek cserélődnek.
3. Ez a folyamat ismétlődik, amíg az elem a megfelelő pozícióba nem kerül, helyreállítva a halom tulajdonságait.

Így a heap push biztosítja az elem hozzáadását a halom sorrendjének megőrzésével, lehetővé téve a minimális vagy maximális elem hatékony kivonását.

Példa Pythonban a heapq modul használatával:

import heapq

heap = [1, 3, 5, 7]
heapq.heapify(heap)  # A listát halommá alakítja

heapq.heappush(heap, 2)  # Hozzáadja az 2-es elemet
print(heap)  # Halom, amely megőrzi a sorrendet

Ennek eredményeként az 2-es elem hozzáadódik és "felszínre kerül" a halom tetejére, megőrizve a min-halom tulajdonságait.