Kas yra stekas (duomenų struktūrų kontekste)?

Aukštynas (heap) — tai specializuota medžio struktūra, naudojama kaip duomenų struktūra. Pagrindinė aukštyno savybė — dalinė tvarka: kiekvienam medžio mazgui taikomas sąlyga, kad tėvo reikšmė yra didesnė arba lygi bet kurios iš jo vaikų reikšmei (max-heap) arba mažesnė arba lygi (min-heap).

Pagrindinės savybės:

• Dvejetainis medis: Dažniausiai įgyvendinamas kaip dvejetainis medis, kur kiekvienas mazgas turi ne daugiau kaip du vaikus.
• Pilnas dvejetainis medis: Visuose lygiuose, išskyrus galbūt paskutinį, medis yra visiškai užpildytas. Paskutinio lygio mazgai užpildomi iš kairės į dešinę. Tai leidžia efektyviai saugoti aukštyną kaip masyvą.
• Aukštyno savybė:
  • Max-heap: Kiekvieno mazgo reikšmė yra didesnė arba lygi jo vaikų reikšmėms. Didžiausias elementas visada yra viršuje.
  • Min-heap: Kiekvieno mazgo reikšmė yra mažesnė arba lygi jo vaikų reikšmėms. Mažiausias elementas visada yra viršuje.

Pagrindinės operacijos su aukštynu:

• Elemento įterpimas: Pridedamas naujas elementas ir išlaikoma aukštyno savybė.
• Elemento šalinimas: Šalinamas šakninis elementas (maksimalus arba minimalus, priklausomai nuo aukštyno tipo) ir išlaikoma aukštyno savybė.
• Aukštyno kūrimas: Aukštyno sudarymas iš masyvo.

Aukštyno taikymas:

• Rikiavimas: Heapsort algoritmas.
• Prioritetinių eilių: Efektyvi įgyvendinimas, kai elementai apdorojami pagal prioritetą.
• Paieškos algoritmai: Pavyzdžiui, k-ojo pagal dydį elemento paieška.
• Grafų algoritmai: Pavyzdžiui, Dijkstros algoritmas.

Aukštyno vaizdavimas masyvu:

Kadangi aukštynas yra pilnas dvejetainis medis, jį galima efektyviai saugoti masyve be nuorodų.

• Jei mazgas yra indeksu i, jo kairysis vaikas yra indeksu 2*i + 1.
• Jo dešinysis vaikas yra indeksu 2*i + 2.
• Jo tėvas yra indeksu (i - 1) / 2.

# Min-heap pavyzdys kaip masyvas
heap_array = [10, 15, 20, 17, 25, 30]

# Šaknys: heap_array[0] = 10
# Kairysis vaikas: heap_array[2*0 + 1] = heap_array[1] = 15
# Dešinysis vaikas: heap_array[2*0 + 2] = heap_array[2] = 20
# Tėvas elemento indeksu 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15