"jendioperatsiooniga" - 1 õppematerjal

Algoritmid ja andmestruktuurid: puud, kuhjad

Eemaldamisülesanne Eemaldada antud binomiaalkuhjast vähima võtmega kirje. ­ Sisend: binomiaalkuhi. ­ Väljund: vähima võtmega kirje. 2 Binomiaalkuhjad 43 2.1 Operatsioonid Lahendusalgoritm Kui kuhi on tühi, siis lõpetatakse ebaõnnestumisega. Vastasel korral ­ otsitakse üles puu, mille juure kirje võti on vähim; ­ käsitledes metsa puude järjendina, tõmmata see puu vastava jär- jendioperatsiooniga kuhjast välja; ­ ühendatakse eemaldatud puu harude mets eemaldamisel järele jäänud kuhjaga; ­ tagastatakse eemaldatud puu juure kirje. 2 Binomiaalkuhjad 44 2.1 Operatsioonid Keerukus Kõik algoritmid on keerukusega O(log n), kus n on kuhja tippude arv (ühendamise puhul kahe kuhja tippude koguarv).