Kruskalov algoritem/Kopica

Iz MaFiRaWiki

public class Kopica {
/*
  Razred Kopica - KOPICA iz povezav JE PREDSTAVLJENA S TABELO, za n podatkov potrebujemo
  tabelo dolzine 3n, ker vanjo zapored zapisujeo ceno in obe krajisci povezave.
*/
 
   private int[][] kop; //tabela, ki predstavlja kopico
   private int m;    //velikost kopice
 
   //konstruktorji:
 
   public Kopica(int velikost) { //naredi prazno kopico dane velikosti
      kop = new int[velikost][3];
      m = velikost;
   }
 
   public Kopica(int[][] matrika){
      //zlozi elemente iz matrike n*n v kopico
 
      int n = matrika.length;
      //velikost kopice, stevilo povezav v zgornjitrikotni matriki
      m = n * (n - 1) / 2; 
      kop = new int[m][3];
      //stevec v kopici
      int k = 0; 
      for (int i = 0; i < n; i++) {
         for (int j = i + 1; j < n; j++) {
            kop[k][0] = matrika[i][j];
            kop[k][1] = i;
            kop[k][2] = j;
            k++;
         }
      }
      //dejanska velikost kopice
      m = k; 
      narediKopico();
   } //konstruktor
 
   public Kopica(int[][] matrika, int neskoncno){
      //zlozi elemente iz matrike n*n v kopico, elemente, ki imajo vrednost neskoncno, izloci
 
      int n = matrika.length;
      //max velikost kopice, povezav bo najvec toliko
      m = n * (n - 1) / 2; 
      kop = new int[m][3];
      //stevec v kopici
      int k = 0; 
      for (int i = 0; i < n; i++) {
         for (int j = i + 1; j < n; j++) {
            //neskoncne povezave takoj izlocimo, da bo manj dela
            if (matrika[i][j] < neskoncno) { 
               kop[k][0] = matrika[i][j];
               kop[k][1] = i;
               kop[k][2] = j;
               k++;
            }
         }
      }
      //dejanska velikost kopice 
      m = k; 
      narediKopico();
   } //konstruktor
 
   //druge metode:
 
   public int[] povejVrh() {
      int[] r = new int[3];
      r[0] = kop[0][0];
      r[1] = kop[0][1];
      r[2] = kop[0][2];
      return r;
   }
 
   public int[] povejZadnjega() {
      int[] r = new int[3];
      r[0] = kop[m-1][0];
      r[1] = kop[m-1][1];
      r[2] = kop[m-1][2];
      return r;
   }
 
   public void spremeniVrh(int[] podatek) {
 
      if(podatek.length != 3) System.out.println("Napaka!");
      //s preverjanjem podatkov se sicer nisem ukvarjala, marsikje bi morali biti 
      // podobni "lovilci"
      else {
         kop[0][0] = podatek[0];
         kop[0][1] = podatek[1];
         kop[0][2] = podatek[2];
      }
   }
 
   public void brisi() {
 
      //zadnjega premaknemo na vrh, nato ga potopimo
      spremeniVrh(povejZadnjega()); 
      m--;
      popraviKopico(0);
   }
 
   /*
      najbolj pomembni metodi,
      s prvo naredimo kopico, z drugo pa vzdrzujemo strukturo kopice pri vstavljanju 
      ali brisanju
    */
 
   public void narediKopico(){
      //iz neurejene tabele naredi kopico
 
      for (int k = m - 1; k >= 0; k--) {
         if (kop[k][0] < kop[(k - 1)/2][0]) {
            zamenjaj(k, (k - 1)/2);
            //od m/2 naprej so listi, teh ni treba
            if (k < m/2 - 1) popraviKopico(k); 
            //prestavljati; indeksi so za 1 manjsi, ker zacnemo z 0
         }
      }
   }
 
   private void popraviKopico(int k){
      //potopi k-ti element do koder je treba
      //ce je oce vecji od manjsego sina
      if ((2*k + 1 < m) && (kop[k][0] > Math.min(kop[2*k + 1][0],kop[2*k + 2][0]))) {
         if (kop[2*k + 1][0] < kop[2*k + 2][0]) {
            zamenjaj(k, 2*k + 1);
            //rekurzivno gremo do listov - v smeri manjsega sina
            popraviKopico(2*k + 1); 
         }
         else {
            zamenjaj(k, 2*k + 2);
            //drugi sin 
            popraviKopico(2*k + 2); 
         }
      }
   }
 
   private void zamenjaj(int k, int j) {
 
      int[] pom = new int[3];
      for (int i = 0; i < 3; i++) {
         pom[i] = kop[k][i];
         kop[k][i] = kop[j][i];
         kop[j][i] = pom[i];
      }
   }
 
   public int velikost() {
      return m;
   }
}class Kopica