Kuhi (informaatika)

Allikas: Vikipeedia
Kuhja struktuur

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.

Tavaliselt esitatakse kuhi arvuti mälus kahendpuuna selliselt, et juurelement on järjendi esimene element, sellele järgnevad juure kaks alamtippu, seejärel nende alamtippude neli alamtipppu jne. Sellisel 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 | redigeeri lähteteksti]

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

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