"allaviimist" - 1 õppematerjal

Algoritmid ja andmestruktuurid: puud, kuhjad

1 Kahendkuhjad 18 1.1 Operatsioonid Keerukus Eeldusel, et võrdlusoperatsioonid ja vahetused on O(1), toimub suuri- ma võtmega kirje eemaldamine ­ halvimal ja keskmisel juhul keerukusega (log n), ­ parimal juhul keerukusega (1). 1 Kahendkuhjad 19 1.1 Operatsioonid Kuhjaparandused Ühe vales positsioonis asuva kirje mullina üles- või allaviimist nime- tatakse kuhjaparanduseks. ­ Need aitavad ka juhul, kui ühes kindlas positsioonis kirje võti muutub. 1 Kahendkuhjad 20 1.1 Operatsioonid Massiivi täitumise probleem Kui kahendkuhi esitada massiivina, siis tasub massiivi suurus võtta va- ruga, et täitumist tuleks ette küllalt harva. Nt võtta massiiv pikkusega 2n - 1 (täieliku kahendpuu suurus) ja kui