Heap.java

/*
 *     YAV (Yet another Visualiser)
 *     (c) 2004 by Robin Quast
 *    Version 1.0 (04.03.2004)
 *    
 *  erstellt im Rahmen der Diplomarbeit
 * "Theorie und Java- Realisierung
 *  ausgewählter Algorithmen zur
 *  Bestimmung kürzester Wege in Graphen"
 *
 *  betreut durch Prof. Dr. Lenze
 *  an der Fachhochschule Dortmund
 *  im SS 2003/ WS 2003/2004
 *
 *  @(#)Heap.java  1.0 04/03/09
 */

import java.util.Vector;
import java.util.Collections;
import java.util.Enumeration;
 
/** Einfache Implementierung eines Heaps (Prioritätswarteschlange) mittels 
 * Vectoren. Für die
 * geringe Anzahl an Knoten und Kanten wird diese Implementation schnell
 * genug sein, um mittels Dijkstra einen kürzesten Weg zu ermitteln. 
 * Reicht diese Implementierung nicht aus, dann kann z.B. auf Skiplisten, oder
 * Fibonacci Heaps zurückgegriffen werden. Zu Skiplisten gibt es im Internet
 * die ein oder andere Implementation (z.B. bei http://iamwww.unibe.ch/~wenger).
 * Der Heap wird nur in der Routine getMin(), bzw. findAndRemoveMin() sortiert, 
 * damit das Element mit dem 
 * kleinsten Schlüssel zurückgegeben werden kann. Wird diese Methode nicht benutzt,
 * dann kann der Heap auch als einfache Warteschlange benutzt werden.
 */ 
 
public class Heap extends Vector {
  
  /** Hinzufügen eine HeapElements. Dieses wird intern in ein Object gecastet 
   * und im Heap eingefügt.
   */
  public void add(HeapElement he) {
    this.add((Objecthe);
  }
  
  /** Fügt ein Element in den Heap ein. Kommt das Element in dem Heap schon vor, so 
   * wird das schon enthaltende Element gelöscht und das neue Element eingefügt.
   */
  public void addOrReplace(HeapElement hel) {
    HeapElement he=find(hel.getNode());
    if (he.getNode()!=nullthis.remove((Objecthe);
    this.add((Objecthel);
  }
  
  /** Löscht das HeapElement, wenn es in dem Heap enthalten ist.
   */
  public void remove(HeapElement he) {
    this.remove((Objecthe);
  

  /** Sucht das Minimum und löscht es aus dem Heap. Das Minimum, also das 
   * Element mit dem kleinsten Schlüssel (HeapElement muss also das Interface
   * Comparable implementieren) wird anschliessend aus dem Heap gelöscht.
   */
  public HeapElement findAndRemoveMin() {
    HeapElement he = getMin();
    remove(he);
    return he;
  

  /** holt das erste Element und löscht es aus dem Heap. Dabei ist der Wert
   * des Elements egal.
   */
  public HeapElement findAndRemoveFirstElement() {
    HeapElement he =(HeapElementfirstElement();
    remove(he);
    return he;
  }

  /** Prüft, ob ein Element in dem Heap enthalten ist.
   */
  public boolean contains(HeapElement he) {
    return this.contains((Objecthe);
  }
  
  /** Gibt das Minimum aus dem Heap zurück. Dabei wird der Heap zunächst 
   * sortiert, damit das Element mit dem kleinsten Schlüssel an erster Stelle 
   * steht.
   */
  public HeapElement getMin() {
    HeapElement min_node = null;
    if (this.size()!=0){
      Collections.sort(this);
      min_node=(HeapElement)this.firstElement();
    }
    return min_node;
  }
  
  /** Suchen und zurückgeben des Elements mit dem kleinsten Schlüssel.
   */
  public HeapElement findMin() {
    return getMin();
  }
  
  /** &auml;ndert den Schl&uuml;ssel des Elements <I>he</I>. Dabei wird das Element 
   <I>he</I> aus dem Heap gel&ouml;scht, der neue
   *  Schl&uuml;ssel von <I>he</I> gesetzt und anschliessend
   * in dem Heap eingef&uuml;gt.
   */
  public void decreaseKey(HeapElement he, int new_key) {
    remove (he);
    he.setKey(new_key);
    add(he);
  }
  
  /** Das Element mit dem Knoten <i>n</I> wird gesucht und 
   * wenn es gefunden wird zur&uuml;ckgegeben. Wird es nicht gefunden,  
   * dann wird ein initialisiertes HeapElement zur&uuml;ckgegeben.
   */
  public HeapElement find (Node n) {
    HeapElement he = new HeapElement();
    boolean gefunden=false;
     Enumeration heap_enum = elements();
    while (heap_enum.hasMoreElements() && !(gefunden)) { 
       HeapElement tmp_element=(HeapElementheap_enum.nextElement();
       if (tmp_element.getNodeValue()==n.getValue()) {
         he=tmp_element;
         gefunden=true;
       }
    }
    return he;
  }
  
  /** Ermittel die Kosten eines Elements mit dem Knoten <i>n</I>.
   */
  public int getCost(Node n) {
    HeapElement he = find(n);
    if (he.knoten!=nullreturn he.getKey();
    else return Integer.MAX_VALUE;
  }  
    
  /** Setze die Kosten f&uuml;r das Element mit dem Knoten <i>n</I> auf <I>cost</I>.
   */
  public void setCost(Node n,int cost) {
    HeapElement he = find(n);
    
    if ((he.getNodeValue()!=-1&& (he.getNode()!=null)) {
      remove(he);
      he.setKey(cost);
      add(he);
    }

  }  
  
/*    public static void main(String[] args) {
      // test
      
      System.out.println("Testen der Heap Klasse.\n");
      System.out.println("Anlegen des HeapElements mit Knoten 3 und Schl&uuml;ssel 7...");
      Node drei = new Node(3); 
      HeapElement he1=new HeapElement(drei,7);
      System.out.println(he1+"\n");
    System.out.println("Anlegen des HeapElements mit Knoten 4 und Schl&uuml;ssel 5...");
      Node vier = new Node(4); 
      HeapElement he2=new HeapElement(vier,5);
      System.out.println(he2+"\n");
    
    System.out.println("Einf&uuml;gen von (3,7),(0,6)");
    Heap h = new Heap();
    h.add(he1);
    h.add(new HeapElement(new Node(0),6));
    System.out.println(h);
    
    System.out.println("Einf&uuml;gen von (4,5)");
    h.add(he2);
    System.out.println(h);
    
    System.out.println("h.getMin()="+h.getMin());
  
    System.out.println("h.findAndRemoveMin()"+h.findAndRemoveMin());
    System.out.println(h);
    
    System.out.println("h.remove(3,7)");
    h.remove(he1);
    System.out.println(h);
  
  }  

  */
}