Algoritem za urejanje s kopico
Iz E-študij, proste zakladnice študentskega znanja
Sortirani elementi so razdeljeni na urejeni (običajno desni) del in na neurejeni del (običajno levi).
Urejamo tako, da najprej zgradimo kopico. Običajno za koren kopice izberemo 1. element v tabeli. Neurejeno kopico zgradimo oz. uredimo od spodaj navzgor.
Binarno drevo pa se da tudi lepo zgraditi v tabeli. Vsak oče ima dva sinova, in sicer če je oče i, potem sta v sistemih, kjer indeksi začnejo z 1, sinova 2i in 2i+1, kjer pa indeksi začnejo z 0, pa sta sinova 2i+1 in 2i+2. V polni kopici so listi vsi elementi v neurejenem delu od n/2 naprej, če je neurejeni del dolg n.
Grajenje kopice in vstavljanje najmanjšega elementa ni časovno tako potratno, dražje je popravljanje kopice.
Časovna zahtevnost algoritma
| T(n) | = T(gradnja kopice) + nT(popravljanje kopice) = |
| = O(n) + nlog(n) | |
| = O(nlogn) |
Postopek
Kopica mora biti obratno urejena kot želimo podatke urediti na izhodu.
Primer urejanja v tabeli v naraščajočem vrstnem redu
- delamo iz desne proti levi in gledamo ali sta oba sinova manjša od očeta
- tako uredimo celotno drevo
- izločimo koren (največjega), tako da ga zamenjamo z zadnjim v tabeli, in ta element imamo za urejeni del tabele
- ponovimo 1 korak na za ena zmanjšani tabeli na podoben način delamo tudi grafični način
