Kahendkuhi: eelistusjärjekord massiivis

Massiivis on viisteist võtit. Sama massiivi saab vaadata puuna: kohal i oleva võtme lapsed asuvad kohtadel 2i + 1 ja 2i + 2. Ehita kuhi ükshaaval lisades või viimasest vanemast alustades ning jälgi iga võrdlust ja vahetust. Seejärel võta väikseim võti välja ja vaata, kuidas järgmine tema kohale tõuseb.

Näidisarvutus — Kahendkuhi: eelistusjärjekord massiivis

Võtmete arv	15
Võrdluste ülempiir ükshaaval lisades	34
Võrdluste ülempiir viimasest vanemast alustades	22
Kuhjade arv 15 erineva võtme korral	21 964 800 / 1 307 674 368 000

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Kahendkuhi: eelistusjärjekord massiivis

Kahend-miinimumkuhi on massiiv, milles kohal i olev võti pole suurem kui võtmed kohtadel 2i + 1 ja 2i + 2, tema lapsed. Koha i vanem asub kohal ⌊(i − 1) / 2⌋. Nii vaadates moodustab massiiv kahendpuu, mille kõik tasemed peale viimase on täis ja viimane täitub vasakult paremale. Väikseim võti on alati kohal 0 ehk juures. Võtme lisamiseks pane see massiivi lõppu ja nihuta üles: vaheta võtit vanemaga seni, kuni võti on vanemast väiksem. Väikseima väljavõtmiseks vii viimane võti juureks ja vajuta alla: vaheta seda väiksema lapsega seni, kuni laps on temast väiksem. Sel viisil kasutatav kuhi on eelistusjärjekord.

Mida iga sümbol tähendab

n: võtmete arv kuhjas
i: koht massiivis, nummerdamine algab 0-st
h: koha kõrgus ehk selle all olevate tasemete arv, ⌊log₂(n / (i + 1))⌋

Eeldab: Võrdlus võrdleb üht võtit teisega, vahetus vahetab kahe koha võtmed. Viimase võtme viimine juureks väljavõtmise ajal ei lähe kummagi alla. Kui võti on võrdne oma vanema või väiksema lapsega, jääb see paigale. Kahe võrdse lapse hulgast valitakse vasak. Siinne kuhi hoiab väikseimat võtit tipus; maksimumkuhjas on kõik võrdlused vastupidised. Kasutada saab kuni viitteist võtit vahemikus 0 kuni 99, et kogu puu mahuks telefoni ekraanile. Viimases reas loendatakse erinevate võtmete järjestusi.

Ükshaaval lisades loeb sügavus, viimasest vanemast alustades kõrgus 🖖

Vajuta Kahanev, ükshaaval. Iga uus võti on kõigist kuhjas olevatest võtmetest väiksem ja tõuseb alt juureni. Iga taseme kohta kulub üks võrdlus ja üks vahetus: juurele 0, järgmisele 2 võtmele kummalegi 1, järgmisele 4 võtmele igaühele 2 ning viimasele 8 võtmele igaühele 3. Kokku 34. Nüüd vajuta Kahanev, alt üles. Samad 15 võtit pannakse massiivi saabumise järjekorras. Lastega kohtadel olevad võtmed vajutatakse alla, alustades kohalt 6 ja liikudes kohani 0. Võti saab laskuda vaid nii mitu taset, kui tema all on. 15 kohast on 8 lehed, mille all pole midagi. Esimese meetodi puhul kulus neil kõigil 3 taseme jagu tööd, siin ei kulu midagi. Kõrguste summa on 11 ja iga taseme kohta tehakse kaks võrdlust: kokku 22. Igas kuhjas on kõrguste summa n miinus ühtede arv n-i kahendesituses, mistõttu kulub selliseks ehitamiseks alati vähem kui 2n võrdlust. Kui 1 023 võtit saabuvad suurimast väiksemani, vajavad need meetodid vastavalt 8 194 ja 2 026 võrdlust.

Väiksemad enne: mõlemal ehitusviisil kulub 14 võrdlust 🖖

Vajuta Kasvav, ükshaaval. Ükski uus võti pole oma vanemast väiksem: lisamiseks kulub üks võrdlus ja vahetust pole vaja. Kokku 14 võrdlust. Vali Viimasest vanemast ja saad jälle 14, sest iga vanema puhul võrreldakse tema lapsi omavahel, seejärel väiksemat last vanemaga ning rohkem tööd polegi vaja. Mõlema meetodi alampiir on 14: iga võtit peale juure tuleb vähemalt korra võrrelda. Sellest piirist ülespoole hakkavad meetodite tulemused erinema. Suurimast väiksemani saabuvad võtmed viivad ükshaaval lisamise võrdluste arvu ülempiirini. Segatud järjekorras võtmetega jääb see palju lähemale alampiirile. Kui 1 000 võtit segati 200 korda, kulus ükshaaval lisamiseks keskmiselt 2 235 võrdlust ja alt üles ehitamiseks 1 862. Samade võtmete saabumisel suurimast väiksemani kulus ükshaaval lisamiseks 7 987 võrdlust. 15 võtmega on vahe väike: vajuta paar korda Sega ja ükshaaval lisamine võib mõnikord võita.

Kuhi ei taga veel sorditud järjekorda 🖖

Kuhi tagab ühe omaduse: ükski võti pole oma lastest suurem. 7 erineva võtme 5 040 võimalikust järjestusest vastavad sellele tingimusele 80. Väikseim võti peab olema juures. Ülejäänud 6 võtmest võivad vasaku alampuu moodustada mistahes 3 ning kumbki alampuu peab samuti olema kuhi. Kuhjade arvu saame, jagades 7! kõigi alampuude suuruste korrutisega 7 · 3 · 3. 15 võtme korral näitab tulemuste tabel 21 964 800 kuhja kokku 1 307 674 368 000 järjestuse seas. Neist vaid üks on sorditud. See valikuvabadus teebki kuhja ehitamise odavaks. Sorditud järjekord tekib võtmeid ükshaaval välja võttes. Vajuta Kuhjasortimine. Iga kord, kui juur välja võetakse, täidab viimane võti vabanenud koha ja vajub alla, nii et järgmine väikseim tõuseb juureks. 12 võtit väljuvad järjekorras 3, 7, 12 ja nii edasi kuni arvuni 93.

Ülesanne täielikult lahendatud

Mitu võrdlust kulub kummagi ehitusviisiga tuhande võtme korral? 4 sammu
Vajuta Kahanev, ükshaaval ja seejärel Kahanev, alt üles ning selgita, kust tulevad 34 ja 22. Nüüd olgu võtmeid 1 023 ja saabugu need suurimast väiksemani. Mitu võrdlust teeb kumbki meetod?

Ava see ülesanne tööriistas
1. Koht i asub sügavusel ⌊log₂(i + 1)⌋: sügavusel 0 on 1 koht, sügavusel 1 on 2, sügavusel 2 on 4 ja sügavusel 3 on 8 kohta. Kui võtmed saabuvad suurimast väiksemani, on iga uus võti seni saabunutest väikseim ja tõuseb juureni. Iga taseme kohta kulub üks võrdlus ja üks vahetus: 0 + 2 · 1 + 4 · 2 + 8 · 3 = 34.
  
  $0 + 2 \cdot 1 + 4 \cdot 2 + 8 \cdot 3 = 34$
2. Viimasest vanemast alustades loeb kõrgus: juurel on see 3, kohtadel 1 ja 2 on see 2, sügavusel 2 olevatel 4 kohal on see 1 ning 8 lehel 0. Kõrguste summa on 11. Suurimast väiksemani saabunud võtmete puhul vajub iga võti lõpuni alla. 15 võtmega on igal vanemal kaks last, mistõttu kulub igal tasemel kaks võrdlust: kokku 22 võrdlust ja 11 vahetust.
  
  $3 + 2 \cdot 2 + 4 \cdot 1 = 11, 2 \times 11 = 22$
3. 1 023 = 2¹⁰ − 1 võtit moodustavad 10 täis tasemega puu, kus sügavusel d on 2ᵈ kohta. Ükshaaval lisamisel kulub võrdlusi sügavuste summa jagu: 1 · 2 + 2 · 4 + 3 · 8 + ⋯ + 9 · 512 = 8 194 võrdlust ja sama palju vahetusi.
  
  $d = 0 \sum 9 d \cdot 2^{d} = 8 \cdot 2^{10} + 2 = 8194$
4. Viimasest vanemast alustades kulub võrdlusi kõrguste kahekordse summa jagu. Kõrgusega 0 kohti on 2⁹, kõrgusega 1 kohti 2⁸ ja nii edasi kuni juureni, mille kõrgus on 9: 1 · 256 + 2 · 128 + ⋯ + 9 · 1 = 1 013. See on 1 023 miinus 10 ühte selle arvu kahendesituses. Kahekordne summa annab 2 026 võrdlust; vahetusi on 1 013.
  
  $h = 0 \sum 9 h \cdot 2^{9 - h} = 1023 - 10 = 1013, 2 \times 1013 = 2026$
Vastus

Ükshaaval lisades 8 194 võrdlust, viimasest vanemast alustades 2 026, seega ühe võtme kohta ligikaudu kaheksa võrdlust või kaks. Enamik kuhja kohti on suure sügavuse ja väikese kõrgusega: lisamise töömahu määrab sügavus, viimasest vanemast alustava ehituse oma kõrgus. Tööriistas saab kasutada kuni viitteist võtit. Sama arvutus annab seal kuvatavad 34 ja 22.

$8194 against 2026$

Õpitee

Mida andmestruktuur võimaldab odavalt teha

Allikad (2)

Heapsort as first published: J. W. J. Williams, "Algorithm 232: Heapsort," Communications of the ACM 7(6), 347–348, June 1964.
The heap-based sort published six months later, close to the version used today: Robert W. Floyd, "Algorithm 245: Treesort 3," Communications of the ACM 7(12), 701, December 1964.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.