Kas ir kaudze?

Kaudze (heap) ir īpaša koka struktūra, kas atbilst kaudzes īpašībai. Šī īpašība nosaka, ka katrā virsotnē, izņemot sakni, šīs virsotnes atslēgas vērtība ir noteiktā attiecībā ar tās vecāka atslēgas vērtību. Ir divi galvenie kaudzes tipi:

• Maksimālā kaudze (Max-heap): Katras virsotnes atslēgas vērtība nav mazāka par tās bērnu atslēgas vērtībām. Lielākais elements atrodas saknē.
• Min-kaudze (Min-heap): Katras virsotnes atslēgas vērtība nav lielāka par tās bērnu atslēgas vērtībām. Mazākais elements atrodas saknē.

Kaudze parasti tiek realizēta kā masīvs, kas ļauj efektīvi piekļūt elementiem un veikt operācijas. Attiecība starp vecākiem un bērniem masīvā ir šāda:

• Elementam ar indeksu i (sākot no 0), tā kreisais bērns ir indeksā 2i + 1.
• Tā labais bērns ir indeksā 2i + 2.
• Tā vecāks ir indeksā floor((i - 1) / 2).

Galvenās operācijas uz kaudzes:

• Ievietošana (Insert): Jauna elementa pievienošana. Laika sarežģītība O(log n), kur n ir elementu skaits.
• Extract-Max / Extract-Min: Maksimālā (max-heap) vai minimālā (min-heap) elementa noņemšana un atgriešana. Laika sarežģītība O(log n).
• Heapify (Kaudzes veidošana): Nejauša masīva pārvēršana kaudzē. Laika sarežģītība O(n).

Kaudzes tiek izmantotas šķirošanas algoritmos (piemēram, heapsort), prioritāšu rindās un īsāko ceļu meklēšanas algoritmos (piemēram, Dijkstra algoritms).