Urejanje s kopico/Implementacija (Java)

Iz MaFiRaWiki

Predpostavka za ponazoritev maksimalne kopice:

  • elementi kopice so shranjeni v tabeli velikosti n: tab [ ]
  • koren kopice se nahaja v tab [1]
  • levi sin vozlišča tab[i] je shranjen v tab [2*i]
  • desni sin vozlišča tab[i] je shranjen v tab [2*i+1]

Algoritem v 4 korakih:

  1. vhodno podatke v tabeli uredimo v maksimalno kopico
  2. ker v urejeni kopici koren vsebuje največjo vrednost, zamenjamo prvi in zadnji element v kopici
  3. popravimo kopico (upoštevamo, da zadnji element ni več v kopici)
  4. ponavljamo koraka 2. in 3., dokler v kopici ne zmanjka podatkov

Postopek potapljanja uporabimo tako v 1. koraku kot v 3. koraku. Kopico, ki ima neustrezen koren, popravimo tako, da koren potopimo po tisti veji, v kateri se nahaja večji sin. Ta postopek ponavljamo, dokler ne pridemo do lista ali dokler ne dosežemo lastnosti kopice.


Primer: Program dobi vhodno neurejeno tabelo:

10 8 25 15 16 3 5 13 9

Program s potaplanjem elementov tabelo najprej uredi v maksimalno kopico, kar pomeni, da je vsak element v korenu večji od svojih sinov, npr.:

25 16 10 15 3 8 5 13 9

To tabelo nato ureja tako, da zaradi lastnosti maksimalne kopice njene največje elemente v vsakem prehodu postavlja na konec tabele. Ko se program konča, dobimo tabelo, v kateri so elementi urejeni od najmanjšega do največjega.

3 5 8 9 10 13 15 16 25

  1. public static void uredisKopico(int[]tab){
  2.  
  3. /* Program, ki uredi elemente dane tabele po velikosti. Najprej uredi tabelo v kopico. Uporabi
  4. postopek potapljanja. Elementi v desni polovici tabele nimajo naslednikov, zato potapljanje ni
  5. potrebno. Preostale elemente, od sredine do začetka tabele, potaplja. */
  6. /* ponavljajamo dokler ne pregledamo vse kandidate za očeta*/
  7. for (int k = tab.length/2; k > =1; k--)
  8. vstavi(tab, k, tab.length);
  9.  
  10. /* metoda, ki potaplja element v smeri večjega sina, uredi tabelo v kopico in ohrani
  11. njeno urejenost */
  12.  
  13. public static void vstavi(int[]tab, int i, int n){
  14. int element = tab[i];
  15. int sin = 2*i;
  16. while (sin <= n) { /*ponavljamo, dokler je kanditat za sina znotraj kopice*/
  17. if (sin < n && tab[sin] < tab[sin+1] ) /* izberemo večjega sina*/
  18. sin++;
  19. /* izvajanje zanke ustavimo, če je element večji ali enak sinu*/
  20. if (element >= tab[sin]) break;
  21. else
  22. tab[i] = tab[sin]; /* če je sin večji ga preaknemo navzgor*/
  23. i = sin; /* indeks elementa pa dobi indeks svojega sina*/
  24. sin = 2*i /* preverimo, če je treba potopiti še ''novega'' sina */
  25. }
  26. a[i] = element; //* naš element zasede mesto z indeksom i v tabeli */
  27. }
  28. for (int n = tab.length; n > 1; n--) { /* ponavljamo, dokler v kopici ne zmanjka podatkov */
  29. element = tab[1]; /* zamenjamo prvi in zadnji element v kopici */
  30. a[1] = tab[n];
  31. a[n]= element;
  32. /* popravimo kopico tako da potopimo koren in upoštevamo da zadnji element ni več v kopici */
  33. vstavi (tab,1,n-1);
  34. }
  35. }
Osebna orodja