Urejanje s kopico

Iz MaFiRaWiki

Vsebina


Urejanje s kopico je algoritem za urejanje podatkov, ki uporablja podatkovno strukturo kopica. Uporabljamo popolnoma levo poravnano drevo. To pomeni, da so vsi listi na nivoju n bolj levo kot listi na nivoju (n - 1).

Urejamo tako, da največji element, ki je tudi koren kopice, odstranimo in zapišemo v tabelo. Nato poskrbimo, da na mesto korena vstavimo zadnji element kopice. Element potopimo v za en element zmanjšani kopici. Ponavljamo, dokler se kopica ne skrči v en sam element. Najmanjši element bo prvi element tabele, največji pa zadnji element tabele.

Rezultat je tabela, urejena v naraščajočem vrstnem redu.

V primeru, da bi imeli min oz. minimalno kopico, bi imeli v korenu najmanjši element kopice.

Primer urejanja:

Imamo vhodno tabelo, kjer so podatki že urejeni v maksimalno kopico, kar pomeni, da je vsak element v korenu večji od svojih sinov:

25 16 10 15 3 8 5 13 9


  • odstranimo največji element
  • zapišemo element v tabelo
  • na mesto korena vstavimo zadnji element kopice


Dobimo tabelo

25

in kopico oblike

Potopimo koren v smeri največjega izmed sinov, tako da bo kopica ponovno postala max kopica.

Postopek ponovno ponovimo in sicer:

  • odstranimo največji element
  • zapišemo element v tabelo in sicer na prvo mesto v tabeli
  • na mesto korena vstavimo zadnji element kopice

Dobimo tabelo

16 25

in kopico


Potopimo koren.

Ponavljamo dokler se kopica ne skrči v en sam element, ki je na prvem mestu tabele.

Rezultat:

3 5 8 9 10 13 15 16 25

Implementacija

Glej tudi

Osebna orodja