Kas ir steks (datu struktūru kontekstā)?

Hēaps (heap) ir specializēta koka struktūra, kas tiek izmantota kā datu struktūra. Galvenā hēapa īpašība ir daļēja kārtība: katram koka mezglam ir izpildīts nosacījums, ka vecāka mezgla vērtība ir lielāka vai vienāda ar jebkuras no tās bērniem vērtību (max-heap) vai mazāka vai vienāda (min-heap).

Galvenās īpašības:

• Binārs koks: Visbiežāk tas tiek realizēts kā binārs koks, kur katram mezglam ir ne vairāk kā divi bērni.
• Pilnīgs binārs koks: Visos līmeņos, izņemot iespējams pēdējo, koks ir pilnībā aizpildīts. Pēdējā līmenī mezgli tiek aizpildīti no kreisās uz labo pusi. Tas ļauj efektīvi glabāt hēapu kā masīvu.
• Hēapa īpašība:
  • Max-heap: Katra mezgla vērtība ir lielāka vai vienāda ar tās bērnu vērtībām. Vislielākais elements vienmēr atrodas saknes pozīcijā.
  • Min-heap: Katra mezgla vērtība ir mazāka vai vienāda ar tās bērnu vērtībām. Vismazākais elements vienmēr atrodas saknes pozīcijā.

Galvenās operācijas ar hēapu:

• Elementa ievietošana: Pievieno jaunu elementu un saglabā hēapa īpašību.
• Elementa dzēšana: Dzēš saknes elementu (vislielāko vai vismazāko, atkarībā no hēapa veida) un saglabā hēapa īpašību.
• Hēapa izveide: Veido no masīva.

Hēapa pielietojums:

• Kārtošana: Heapsort algoritms.
• Prioritātes rindas: Efektīva realizācija, kurā elementi tiek apstrādāti pēc prioritātes.
• Meklēšanas algoritmi: Piemēram, meklējot k-tā lielākā elementa.
• Grafu algoritmi: Piemēram, Dijkstras algoritms.

Hēapa attēlojums ar masīvu:

Tā kā hēaps ir pilns binārs koks, to efektīvi var glabāt masīvā bez norādēm.

• Ja mezgls atrodas indeksā i, tā kreisais bērns ir indeksā 2*i + 1.
• Tā labais bērns ir indeksā 2*i + 2.
• Tā vecāks ir indeksā (i - 1) / 2.

# Min-heap piemērs kā masīvs
heap_array = [10, 15, 20, 17, 25, 30]

# Sakne: heap_array[0] = 10
# Kreisais bērns: heap_array[2*0 + 1] = heap_array[1] = 15
# Labais bērns: heap_array[2*0 + 2] = heap_array[2] = 20
# Vecāks elementam ar indeksu 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15