"binomiaalmetsaga" - 1 õppematerjal

Algoritmid ja andmestruktuurid: puud, kuhjad

1 Kahendkuhjad 28 1.2 Järjestamise kuhjameetod Keerukus Järjestamise kuhjameetodi keerukus on O(n log n). 2 Binomiaalkuhjad 29 Binomiaalkuhjad 2 Binomiaalkuhjad 30 Invariant Binomiaalkuhja (ingl binomial heap) puhul nõutakse ­ kuhjatingimust (pööratud järjestuse suhtes) ­ ja et tegu oleks binomiaalmetsaga (metsaga, kus puudeks on paa- rikaupa erinevat järku binomiaalpuud). 2 Binomiaalkuhjad 31 Ülekanduvus alamstruktuuridele Binomiaalkuhja igast tipust lähtuva puu harude mets on binomiaalku- hi. 2 Binomiaalkuhjad 32 Eesmärk Lisaks kahendkuhjas defineeritud operatsioonidele lubab binomiaal- kuhjastruktuur ka kuhjade kiiret ühendamist.