"kuhjastamine" - 1 õppematerjal

Algoritmid ja andmestruktuurid: puud, kuhjad

Nt võtta massiiv pikkusega 2n - 1 (täieliku kahendpuu suurus) ja kui ta saab täis, siis võtta uus massiiv pikkusega 2n+1 - 1 jne. ­ Siis tipu juurdetekitamine viimase taseme lõppu on keskmise keerukusega O(1). 1 Kahendkuhjad 21 1.2 Järjestamise kuhjameetod Järjestamise kuhjameetod 1 Kahendkuhjad 22 1.2 Järjestamise kuhjameetod Kuhjastamine Ülesanne: tekitada kahendkuhi, milles oleksid parajasti samad kirjed nagu antud järjendis. ­ Sisend: järjend. ­ Väljund: samade kirjetega kahendkuhi. 1 Kahendkuhjad 23 1.2 Järjestamise kuhjameetod "Jaga ja valitse" lahendusalgoritm Esiteks tekitada kompaktne kahendpuu, milles oleksid parajasti samad kirjed nagu antud järjendis. (St paigutada tipud kompaktse kahendpuu struktuuri järgi.)