UREJANJE S KOPICO ~ heap sort

UREJANJE S KOPICO ~ heap sort

Avtor: Anja Dulmin

Kopica

Kopica je levo poravnano dvojiško drevo z naslednjimi lastnostmi:

  • element v korenu je večji/manjši od obeh sinov
  • obe poddrevesi korena sta kopici

Glede na te lastnosti ločimo maksimalno in minimalno kopico.



(http://www2.nauk.si/files/693/slika1_0.jpg)
Primer maksimalne in minimalne kopice

Predstavitev kopice s tabelo

Pri urejanju s kopico, kopico pogosto predstavimo s tabelo(seznamom). Elementi kopice so shranjeni v tabeli po naslednjem pravilu:


  • začnemo z indeksom i = 0:

    • oče je na mestu: za i-ti element
    • levi sin =
    • desni sin =
  • začnemo z indeksom i = 1:

    • oče je na mestu: za i-ti element
    • levi sin =
    • desni sin =


PRIMER:

(http://www2.nauk.si/files/693/slika2_2.jpg)
(http://www2.nauk.si/files/693/slika3_1.jpg)
Predstavitev kopice s tabelo
  • Želimo poiskati očeta elementa 13 z indeksom 3:

    • oče = = 1
    • tudi iz slike je razvidno, da je oče element z vrednostjo 20, ta pa je na mestu z indeksom 1
  • Želimo poiskati levega in desnega sina elementa 10 z indeksom 2:

    • levi sin = =
    • desni sin = =
    • tudi iz slike je razvidno, da je levi sin element z vrednostjo 7 in indeksom 4, desni sin pa je element z vrednostjo 5 in indeksom 5

Gradnja maksimalne kopice: 1. način


Elementi prihajajo sproti in vskakega posebej vnašamo v kopico:

  • na začetku vzamemo prva dva elementa in gradimo maksimalno kopico
  • na vsakem koraku dodamo nov element
  • sproti gledamo, da je oče vedno večji od sinov (če bi gradili minimalno kopico, bi gledali, da je oče vedno manjši od sinov)

PRIMER:

Z elementi: 13, 21, 9, 42, 2, 17 ,ki jih dobivamo sproti enega za drugim, želimo zgraditi kopico.

(http://www2.nauk.si/files/693/slika4_0.jpg)

(http://www2.nauk.si/files/693/slika5_0.jpg)



(http://www2.nauk.si/files/693/slika6_2.jpg)

Gradnja maksimalne kopice: 2. način


Tabelo z znanimi elementi preoblikujemo v kopico:

  • prvo mesto v tabeli predstavlja koren kopice
  • začnemo pri vseh poddrevesih in jih uredimo v maksimalno kopico, tako da tekoči element potapljamo v smeri večjega od sinov
  • začnemo pri najnjižjih nivojih in spajamo kopice
  • ponavljamo tako dolgo dokler tega ne storimo tudi za korenski element kopice

PRIMER:

Iz tabele želimo zgraditi maksimalno kopico.

Celoten postopek se dejansko odvija na tabeli, zato ga bomo tudi prikazali na tabeli. S spajanjem "majhnih" kopic gradimo vedno večje kopice. Na koncu zgradimo maksimalno kopico.

(http://www2.nauk.si/files/693/slika7.jpg)
Začetna tabela


Koren poddrevesa se nahaja na mestu z indeksom , kjer je n število elementov v tabeli. Na vsakem koraku se število zmanjša za ena, saj smo poddrevo uredili v maksimalno kopico. Prvi korak se torej začne pri in to je prvo vozlišče, ki ima sina. Nato nadaljujemo s , ..., vse dokler ne pridemo do , ki označuje mesto korena v kopici.

  • k = 4, n = 8:

    • oče je na mestu: = 4 --> element 1
    • levi sin je na mestu: --> element 7
    • desni sin je na mestu: --> element ne obstaja

      (http://www2.nauk.si/files/693/slika8_3.jpg)

  • k = 3, n = 7:

    • oče je na mestu: = 3
    • levi sin je na mestu: --> element 5
    • desni sin je na mestu: --> element 42

      (http://www2.nauk.si/files/693/slika9_4.jpg)

  • k = 2, n = 5:

    • oče je na mestu: = 2
    • levi sin je na mestu: --> element 7
    • desni sin je na mestu: --> element 13

      (http://www2.nauk.si/files/693/slika10_4.jpg)

  • k = 1, n = 3:

    • oče je na mestu: = 1 --> element 2
    • levi sin je na mestu: --> element 13
    • desni sin je na mestu: --> element 42

      (http://www2.nauk.si/files/693/slika11_5.jpg)

(http://www2.nauk.si/files/693/slika11a_1.jpg)

PRIMER: gradnja maksimalne kopice - prikaz s filmčkom

Urejanje s kopico


Urejanje s kopico je algoritem za urejanje podatkov.

Temelji na algoritmu urejanja z navadnim izbiranjem, a za shranjevanje še neurejenih elementov uporablja kopico.
Pri urejanju z navadnim izbiranjem pa gre za to, da v neurejenem delu tabele najdemo najmanjši element in ga vstavimo na konec urejenega dela tabele.

Pri urejanju uporabljamo podatkovno strukturo kopica, ki je bodisi maksimalna, bodisi minimalna, odvisno kako urejamo podatke(naraščajoče ali padajoče).

Uporabljamo dvojiško drevo, ki je levo poravnano. To pomeni, da elemente vstavljamo iz leve proti desni.

Postopek urejanja števil s kopico (naraščajoče)


  • uporabljamo levo poravnano dvojiško drevo
  • imamo maksimalno kopico
  • vemo da je v korenu kopice največji element in da v tabeli spada na zadnje mesto, saj elemente urejamo od največjega do najmanjšega
  • kopici odstranimo zadnji list
(http://www2.nauk.si/files/693/slika12a.jpg)


  • na sproščeni prostor v tabeli, ki ni več del kopice, zapišemo element iz korena kopice
  • v koren kopice pa zapišemo element iz odstranjenega lista
  • torej element v korenu zamenjamo z zadnjim elementom v kopici
  • element v korenu potopimo v smeri največjega od sinov, v za en element zmanjšani kopici, tako da bo kopica spet maksimalna
  • postopek ponavljamo dokler se kopica ne skrči v en sam element, ki je kot tabela urejena
  • najmanjši element bo prvi element seznama, največji element pa bo zadnji
  • če želimo števila urediti padajoče, uporabimo minimalno kopico

PRIMER: urejanje števil s kopico (naraščajoče)

Elemente 2,5,17,1,13,5,42,7 želimo urediti naraščajoče.

Ker za urejanje potrebujemo maksimalno kopico, moramo le to najprej zgraditi. Uporabili bomo končno tabelo, katero smo z 2. načinom gradnje kopice, dobili v prejšnjem poglavju.



(http://www2.nauk.si/files/693/slika12_3.jpg)
Maksimalna kopica/začetna tabela


OPOMBA: Ker urejamo na mestu, bomo elemente, ki "ne spadajo" več v kopico (na vsakem koraku potapljanja elementa, kopico zmanjšamo za en element) označevali z barvo.

Urejanje elementov se ves čas dogaja v tabeli, vendar pa je zaradi lažje predstavljivosti delovanja algoritma, prikazano tudi s pomočjo drevesa.

Ker so elementi znani vnaprej, gre za isti postopek kot pri gradnji kopice. S pomočjo potapljanja elementov v kopici na koncu dobimo urejene elemente v tabeli od najmanjšega do največjega.

(http://www2.nauk.si/files/693/slika13.jpg)



(http://www2.nauk.si/files/693/slika14.jpg)

(http://www2.nauk.si/files/693/slika15_0.jpg)



(http://www2.nauk.si/files/693/slika16_0.jpg)

(http://www2.nauk.si/files/693/slika17.jpg)



(http://www2.nauk.si/files/693/slika18_0.jpg)

(http://www2.nauk.si/files/693/slika19.jpg)

PRIMER: urejanje števil s kopico (naraščajoče) - prikaz s filmčkom

Časovna in prostorska zahtevnost algoritma


  • ČASOVNA ZAHTEVNOST:

    • O(nlogn)
    • gradnja kopice: logn potapljanj
      višina kopice je definirana z vozliščem z najvišjim nivojem - višina kopice = logn
    • število elementov: n


  • PROSTORSKA ZAHTEVNOST:

    • O(1)
    • urejamo na mestu, zato ne potrebujemo dodatnega prostora(dodatnih seznamov)


Na spodnji povezavi si lahko pogledate kodo algoritma v programskem jeziku Python:

KODA algoritma

Koda algoritma - Python


(http://www2.nauk.si/files/693/koda1_0.jpg)



(http://www2.nauk.si/files/693/koda2_0.jpg)

KVIZ

1. NALOGA


Kaj je kopica?


iskalno dvojiško drevo
desno poravnano dvojiško drevo
levo poravnano dvojiško drevo

Pravilno

Odgovor je pravilen. Poskusi rešiti še ostale naloge.

Naprej

Napačno

Odgovor je napačen. Poskusi ponovno.

Ponovi

2.NALOGA


Katera vrsta kopice je predstavljena na sliki?


(http://www2.nauk.si/files/693/kviz1.jpg)


Preveri

Pravilno

Odgovor je pravilen. Poskusi rešiti še ostale naloge.

Naprej

Napačno

Odgovor je napačen. Poskusi ponovno.

Ponovi

3.NALOGA


Podano imamo tabelo z elementi, ki predstavljajo maksimalno kopico. Ustrezno poveži odgovore med seboj.


(http://www2.nauk.si/files/693/kviz2.jpg)


oče elementa 14
levi sin elementa 18
levi in desni sin elementa 25
element 33
ne obstaja
elementa 18 in 13
elementa 14 in 7

Preveri

Pravilno

Odgovor je pravilen. Poskusi rešiti še ostale naloge.

Naprej

Napačno

Odgovor je napačen. Poskusi ponovno. Ponovi

4.NALOGA


Katera od spodnjih slik predstavlja kopico, sestavljeno iz že znanih elementov (2.način gradnje kopice):

13, 7, 2, 19, 5, 1 ?

(http://www2.nauk.si/files/693/kviz3.jpg)
(http://www2.nauk.si/files/693/kviz4.jpg)
(http://www2.nauk.si/files/693/kviz5.jpg)

Pravilno

Odgovor je pravilen. Poskusi rešiti še ostale naloge.

Naprej

Napačno

Odgovor je napačen. Poskusi ponovno.

Ponovi

5.NALOGA


Katere operacije izvajamo pri naraščajočem urejanju s kopico?


Preveri

Pravilno

Odgovor je pravilen.

Naprej

Napačno

Odgovor je napačen. Poskusi ponovno.

Ponovi

VIRI

0%
0%