HeapPos.java

//Prioritetna vrsta, kjer lahko spreminjamo prioritete implementirana s kopico
 
public class HeapPos extends Heap implements PQDecrease  {
  HeapPosNode nodes[];
 
  public HeapPos() {
    this(DEFAULT_SIZE);
  }
  public HeapPos(int maxSize) {
    size = maxSize;
    nodes = new HeapPosNode[size];
    noNodes = 0;
    nodes[0] = null;
  }
 
  public void insert(HeapPosNode 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];
      nodes[newNode].setHeapIndex(newNode) ;
      newNode = parent;
      parent = parent / 2;
    }
    // element prepisemo sele, ko poznamo koncen polozaj
    nodes[newNode] = x;
    nodes[newNode].setHeapIndex(newNode) ;
  }
 
  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 {
      HeapPosNode 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];
        nodes[newNode].setHeapIndex(newNode) ;
        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
      nodes[newNode].setHeapIndex(newNode) ;
      noNodes--; //  kopica se skrajsa za en element
      return retValue;
    }
  }
 
  public void decreaseKey(HeapPosNode x, Comparable pNew) {
    if (x.getKey().compareTo(pNew) > 0) {
      x.setKey(pNew) ;
      int hPos = x.getHeapIndex();
      int parent = hPos / DEGREE ;
      while (parent > 0 && x.compareTo(nodes[parent]) < 0) {
        nodes[hPos] = nodes[parent];
        nodes[hPos].setHeapIndex(hPos) ;
        hPos = parent ;
        parent /= DEGREE ;
      }
      nodes[hPos] = x ;
      nodes[hPos].setHeapIndex(hPos) ;
    }
  }
 
  class HeapPosNodeInt implements HeapPosNode {
    int heapIndex, key ;
    public Comparable getKey() {
      return new Integer(key) ;
    }
    public void setKey(Comparable k) {
      key = ((Integer)k).intValue() ;
    }
    public int getHeapIndex() {
      return heapIndex ;
    }
    public void setHeapIndex(int idx) {
      heapIndex = idx ;
    }
    public int compareTo(Object x) {
      Integer xKey = new Integer(((HeapPosNodeInt)x).key) ;
      return (new Integer(key)).compareTo(xKey) ;
    }
  }
 
  public HeapPosNodeInt prepareIntNode(int k) {
    HeapPosNodeInt x = new HeapPosNodeInt() ;
    x.key = k ;
    x.heapIndex = 0 ;
    return x ;
  }
 
  public static void main(String[] args) {
    HeapPos heap = new HeapPos();
    HeapPosNode el=null  ;
    int elements[] = {
        7, 2, 5, 7, 8, 3, 9};
    System.out.println("Inserting: ");
    for (int i = 0; i < elements.length; i++) {
      el = heap.prepareIntNode(elements[i]) ;
      heap.insert(el);
      System.out.println("inserting " + el.getKey() + " to index " + el.getHeapIndex());
    }
    System.out.println("\nDecreasing " + el.getKey() + " to 4");
    heap.decreaseKey(el, new Integer(4));
    System.out.print("Deleting minimal: ");
    HeapPosNodeInt minEl;
    do {
      minEl = (HeapPosNodeInt)heap.deleteMin();
      System.out.print(minEl.key + ", ");
    }
    while (!heap.empty());
  }
}