"kahendkuhjast" - 1 õppematerjal

Algoritmid ja andmestruktuurid: puud, kuhjad

1 Kahendkuhjad 14 1.1 Operatsioonid Keerukus Eeldusel, et võrdlusoperatsioonid ja vahetused on O(1), toimub lisa- mine ­ halvimal juhul keerukusega O(log n), ­ parimal ja keskmisel juhul keerukusega O(1), kus n tähistab kuhja tippude arvu. 1 Kahendkuhjad 15 1.1 Operatsioonid Eemaldamisülesanne Eemaldada kahendkuhjast suurima võtmega kirje. ­ Sisend: kahendkuhi. ­ Väljund: kuhja vähima võtmega kirje, kui kuhi just tühi ei olnud. 1 Kahendkuhjad 16 1.1 Operatsioonid Lahendus Kui puu on tühi, siis lõpetatakse ebaõnnestumisega. Muidu: ­ likvideeritakse puu viimase taseme viimane tipp; ­ kirjutatakse seal olnud kirje puu juurtippu; ­ viiakse juurtipu kirje mullina alla, nii et taastub kuhjatingimus;