1 Kahendkuhjad 26 1.2 Järjestamise kuhjameetod "Jaga ja valitse" algoritm massiivi puhul · Eeltöö -- kompaktse kahendpuu struktuuri loomine -- on triviaal- ne. Etteantud massiivi võib algusest peale käsitleda nii, nagu ta väl- jendaks kompaktset kahendpuud. Positsioonid massiivis määravad alluva-ülemuse suhted ära. · Põhitöö -- järjest suuremate alampuude muutmine kuhjaks -- on teostatav tsükliga. Läbime massiivi tagurpidi, rakendades iga elemendi juures kirje allaviimist. 1 Kahendkuhjad 27 1.2 Järjestamise kuhjameetod Järjestamine Järjend kuhjastatakse, ning tsüklis eemaldatakse kuhjast suurima võtmega kirje ja lisatakse looda- vasse järjendisse suunaga lõpust alguse poole, kuni kuhi saab tühjaks. Meetod on ebastabiilne.
alampuudeks. Üldine puu – mittelineaarne andmestruktuur, mis koosneb tippudest & kaartest. Andmed paigutatakse tippudesse. Kahendpuu – igal tipul max. kaks alampuud; range vahe vasak- ja parempoolsel alampuul. Järjestatud puu – ühe tipu järglaste järjestus on oluline; räägitakse esimesest, teisest, kolmandast pojast. Järjestamata puu – tipu järglaste järjestus ei ole oluline. Mõisted – sõlme järk (kõigi alampuude arv); leht (alampuudeta sõlm); hargnevad sõlmed (ülejäänud sõlmed); tase (sõlmed jagunevad paiknemise järgi, juur on tase 0, juure järglased tase 1); puu kõrgus (mõõdetakse tasemete järgi); täielik puu (kõigil tasemetel maksimaalne võimalik arv sõlmi & kõik lehed samal tasemel); mets (järjestatud hulk, mis koosneb 0 või mitmest mittelõikuvast puust, kui eemaldada puu juur, saame alampuudest metsa); n-järku puu (puu, mille
kõrguse j vahel eksisteerib seos |x|
Üldine puu • Graaf on mittelineaarne struktuur, mille abil saab modelleerida objektide hulgas paari-kaupa esinevaid suhteid ja seoseid. • Puu on graafi erivorm. • Puus ühendatakse andmeobjektid hierhilisel viisil. • Puu koosneb elementidest, mida nim. tippudeks ehk sõlmedeks (siia paigutakse andmed/info), ja seosetest tippude (sõlmedes oleva info) vahel, mida nim. kaarteks. • Iga puu sõlm on juureks mõnele alampuule. Sõlme kõigi alampuude arvu nimetatakse selle sõlme järguks. Sõlm, mille järk on 0, on leht, Ülejäänud sõlmed on hargnevad sõlmed. • Puu sõlmed jagunevad paiknemishierarhia järgi tasemetesse. Juur on tasemel 0, juure järglased on tasemel 1 jne. Vastavalt tasemete arvule mõõdetakse ka puu kõrgust. • Puu on täielik, kui tema kõigil tasemetel on max võimalik arv sõlmi ja kõik lehed paiknevad samal tasemel.
annaabi.ee 
