Kuhi (informaatika)

(Ümber suunatud leheküljelt Kuhi (andmestruktuur))

Kuhi on informaatikas andmestruktuur, mis põhineb puul ja rahuldab "kuhja tingimust": iga tipu võtmeväärtus on alamtippude omast suurem või sellega võrdne. Kuhja juurelement on ühtlasi ka kõige suurema võtmeväärtusega.

Kuhja struktuur

Tavaliselt esitatakse kuhi arvuti mälus kahendpuuna nii, et juurelement on järjendi esimene element, sellele järgnevad juure kaks alamtippu, seejärel nende alamtippude neli alamtipppu jne. Sel juhul on lihtsasti arvutatav alam- ja ülemtippude asukoht. Kohal i asuva tipu alamtipud asuvad positsioonidel 2i+1 ja 2i+2, kui juurelement on kohal 0. Ülemtipp asub kohal (i-1)/2.

Rakendused

muuda

Kuhi sobib elementide hulgast minimaalse ja maksimaalse väärtuse kiireks leidmiseks.

Kuhja kasutatakse graafi töötlemise algoritmides, näiteks Dijkstra algoritmis.

Vaata ka

muuda