Heap.java

//Prioritetna vrsta implementirana s kopico
 
public class Heap implements PriorityQueue {
  static final int DEFAULT_SIZE = 100 ;
  static final int DEGREE = 2 ;
  Comparable nodes[] ;
  int noNodes, size ;
  public Heap() {
    this(DEFAULT_SIZE) ;
  }
  public Heap(int maxSize) {
    size = maxSize ;
    nodes = new Comparable[size] ;
    noNodes = 0 ;
    nodes[0] = null ;
  }
  public void makenull() {
    noNodes = 0 ;
  }
 
  public void insert(Comparable x) {
    int newNode, parent; // indeks novega vozlisca in njegovega oceta
    noNodes = noNodes + 1;
    newNode = noNodes; // dodamo element na prvo prazno mesto
    parent = newNode / 2; // i-ti element je oce j-tega elementa
    while (parent > 0 && nodes[parent].compareTo(x) > 0) {
      nodes[newNode] = nodes[parent];
      newNode = parent;
      parent = parent / 2;
    }
    // element prepisemo sele, ko poznamo koncen polozaj
    nodes[newNode] = x;
  }
 
  public Comparable deleteMin() {
   int newNode ; // novi indeks prejsnjega zadnjega elementa
   int son ; // indeks manjsega od njegovih sinov
   Comparable temp ;
 if (noNodes == 0)
   return null ; //  error - prazna kopica
 else {
   Comparable retValue = nodes[1]; // minimalni element je v korenu
   newNode = 1; // na zacetku je novi polozaj zadnjega elementa kar v korenu
   if (2 * newNode + 1 <= noNodes) // desni sin obstaja
     if (nodes[2 * newNode].compareTo(nodes[2 * newNode + 1]) < 0)
       son = 2 * newNode;
     else
       son = 2 * newNode + 1;
   else if (2 * newNode <= noNodes) // levi sin obstaja
     son = 2 * newNode;
   else
     son = noNodes + 1; // sin ne obstaja
   while (son <= noNodes && nodes[noNodes].compareTo(nodes[son]) > 0) {
     // manjsi od sinov gre navzgor *)
     nodes[newNode] = nodes[son];
     newNode = son;
     if (2 * newNode + 1 <= noNodes) // desni sin obstaja
       if (nodes[2 * newNode].compareTo(nodes[2 * newNode + 1]) < 0)
         son = 2 * newNode;
       else
         son = 2 * newNode + 1;
     else if (2 * newNode <= noNodes) // levi sin obstaja
       son = 2 * newNode;
     else
       son = noNodes + 1;
   }
   nodes[newNode] = nodes[noNodes]; // bivsi zadnji v kopici se premakne na nov polozaj
   noNodes--; //  kopica se skrajsa za en element
   return retValue;
 }
  }
 
  public boolean empty() {
    return (noNodes == 0 ? true : false) ;
  }
 
  public static void main(String[] args) {
    Heap heap = new Heap();
 
     int elements[] = {7,2,5,7,8,3,9} ;
     System.out.print("Inserting:");
     for (int i=0 ; i < elements.length ; i++) {
       heap.insert(new Integer(elements[i]));
       System.out.print(elements[i]+", ") ;
     }
     System.out.print("Deleting minimal:");
     Comparable minEl ;
     do {
       minEl = heap.deleteMin();
       System.out.print(minEl+", ") ;
     } while ( !heap.empty() ) ;
  }
}