Urejanje s kopico

Grafični prikaz urejanja s kopico

Primer maksimalne kopice

Urejanje s kopico ali urejanje z izboljšanim izbiranjem (angleško HeapSort) je algoritem za urejanje podatkov, ki temelji na algoritmu urejanja z navadnim izbiranjem, a za shanjevanje še neurejenih elementov uporablja maksimalno kopico.

Delovanje

Algoritem na začetku v tabeli iz neurejenih elementov zgradi maksimalno kopico, nato pa se zamenjata koren kopice(največji element) in zadnji list kopice. Ker je element v korenu sedaj manjši od sinov, dobljeno drevo ni kopica - to popravimo tako, da se novi koren rekurzivno zamenjuje z večjim izmed sinov. Lahko rečemo tudi, da se pogreza. Največji element, ki je sedaj na mestu zadnjega lista, pa po zamenjavi ni več del kopice, ampak predstavlja trenutno urejeni del tabele. Ko se postopek zamenjevanja elementov in popravljanja kopice ponavlja, se na desni strani tabele nabirajo urejeni elementi, kopica pa se zmanjšuje. Algoritem se zaključi, ko ima kopica en sam element.

Zahtevnost

Časovna zahtevnost je v vseh primerih $O(n \log n)$, prostorska zahtevnost pa je $O(1)$.

Psevdokoda

  void urediSKopico(tabela[]) {
    //v tabeli zgradimo maksimalno kopico
    zgradiKopico(tabela);
 
    konec = length(tabela)-1;
    do {
      //zamenjamo koren in zadnji list kopice
      zamenjaj(0, konec);
      //zmanjšamo velikost kopice
      konec--;
      //in popravimo kopico
      pogrezniKopico(tabela, 0, konec);
    } while (konec > 0);
  }
  void zgradiKopico(tabela[]) {
    //graditi začnemo z uporabo elementov predzadnjega in zadnjega nivoja
    start = (length(tabela)-2)/2;
    do {
      pogrezniKopico(tabela, start, length(tabela)-1);
      start--;
    } while (start >= 0);
  }
  void pogrezniKopico(tabela[], start, konec) {
    stars = start;
    otrok = start*2+1;
    while (otrok <= konec) {
      //če desni otrok obstaja in je večji od levega, izberemo desnega
      if ((otrok+1 <= konec)&&(tabela[otrok+1] > tabela[otrok]))
        otrok++;
 
      //če je stars večji od otrok imamo kopico in končamo
      if (tabela[stars] >= tabela[otrok]) return;
 
      zamenjaj(stars, otrok);
      //po menjavi gremo en nivo nižje v kopici
      stars = otrok;
      otrok = otrok*2+1;
    }
  }