Ko dara heap push un kā tas pievieno elementu kaudzei?

Heap push — tas ir operācija, kurā tiek pievienots jauns elements „kupa“ (heap) datu struktūrā, kas saglabā kupas īpašības (piemēram, minimālo vai maksimālo).

Kā notiek pievienošana:

1. Jauns elements tiek novietots masīva, kas pārstāv kupu, beigās.
2. Tad tiek veikta "pacelšanās" (sift-up vai bubble-up) operācija: elements tiek salīdzināts ar savu vecāku, un, ja tiek pārkāptas kupas īpašības (piemēram, min-kupā, ja elements ir mazāks par vecāku), elementi tiek apmainīti vietām.
3. Šis process tiek atkārtots, līdz elements atrodas pareizajā pozīcijā, atjaunojot kupas īpašības.

Tādējādi, heap push nodrošina elementa pievienošanu, saglabājot kupas kārtību, kas ļauj efektīvi izņemt minimālo vai maksimālo elementu.

Piemērs Python valodā ar heapq moduli:

import heapq

heap = [1, 3, 5, 7]
heapq.heapify(heap)  # Pārvērš sarakstu kupā

heapq.heappush(heap, 2)  # Pievieno 2
print(heap)  # Kupa ar saglabātu kārtību

Rezultātā, elements 2 tiks pievienots un "pacelts" augšup, lai saglabātu min-kupas īpašības.