Algoritmid ja andmestruktuurid: puud, kuhjad (0)

1
Kuhjad
2
Olemus
Kuhi  (ingl  heap ) on puu või mets, kus:
– igas tipus on üks võtmega kirje,  kusjuures  võtmed on omavahel
võrreldavad;
– kehtib nn kuhjatingimus (ingl heap property): iga tipu kirje
võti on vähemalt niisama suur kui tema suvalise alluva kirje võti.
3
Märkusi
• Tihti kasutatakse ka kuhje, kus kuhjatingimuses nõutakse vastupi-
dist järjestust: iga tipu kirje võti on ülimalt niisama suur kui tema
suvalise alluva kirje võti (nn pöördkuhi (ingl min-heap)).
• Kasutatakse mitut kuhjaliiki, millest igaühe puhul nõutakse lisaks
tingimusi puu struktuuri kohta.
4
Eesmärk
Kuhjad on mõeldud puhuks, kui ühtedeks põhioperatsioonidest on suu-
rima (või vähima) võtmega kirje leidmine ja eemaldamine.
Lisaks neile peab olema võimalik odavalt  sooritada   kirjete  lisamist.
– Sobivad seega eelistusjärjekorra realiseerimiseks.
1
Kahendkuhjad
5
Kahendkuhjad
1
Kahendkuhjad
6
Invariant
Kahendkuhja (ingl  binary  heap) puhul nõutakse