Mis on hunnik?

Hajut (heap) on spetsiaalne puustruktuur, mis vastab heap-omadusele. See omadus ütleb, et iga tipptaseme puhul, välja arvatud juur, peab selle tipu väärtus olema teatud suhtega selle vanema väärtusega. On kaks peamist heap-tüüpi:

• Maksimaalne heap (Max-heap): Iga tipu väärtus ei ole väiksem oma laste väärtusest. Suurim element asub juurtipus.
• Min-heap: Iga tipu väärtus ei ole suurem oma laste väärtusest. Väikseim element asub juurtipus.

Heap on tavaliselt rakendatud massiivina, mis võimaldab tõhusat juurdepääsu elementidele ja operatsioonide teostamist. Massiivis on vanema ja laste vaheline seos järgmine:

• Indeksiga i (alates 0), vasak laps asub indeksil 2i + 1.
• Õige laps asub indeksil 2i + 2.
• Vanem asub indeksil floor((i - 1) / 2).

Heap-i peamised operatsioonid:

• Insert (Sisestamine): Uue elemendi lisamine. Teostusaeg O(log n), kus n on elementide arv.
• Extract-Max / Extract-Min: Maksimaalse (max-heap) või minimaalse (min-heap) elemendi eemaldamine ja tagastamine. Teostusaeg O(log n).
• Heapify (Heap-i ehitamine): Mistahes massiivi muutmine heap-ks. Teostusaeg O(n).

Heap-e kasutatakse sorteerimisalgoritmides (näiteks heapsort), prioriteedijärjekordades ja lühimate teede otsingualgoritmides (näiteks Dijkstra algoritm).