/*
* 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((Object) he);
}
/** 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()!=null) this.remove((Object) he);
this.add((Object) hel);
}
/** Löscht das HeapElement, wenn es in dem Heap enthalten ist.
*/
public void remove(HeapElement he) {
this.remove((Object) he);
}
/** 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 =(HeapElement) firstElement();
remove(he);
return he;
}
/** Prüft, ob ein Element in dem Heap enthalten ist.
*/
public boolean contains(HeapElement he) {
return this.contains((Object) he);
}
/** 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();
}
/** ändert den Schlüssel des Elements <I>he</I>. Dabei wird das Element
* <I>he</I> aus dem Heap gelöscht, der neue
* Schlüssel von <I>he</I> gesetzt und anschliessend
* in dem Heap eingefü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ückgegeben. Wird es nicht gefunden,
* dann wird ein initialisiertes HeapElement zurü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=(HeapElement) heap_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!=null) return he.getKey();
else return Integer.MAX_VALUE;
}
/** Setze die Kosten fü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ü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üssel 5...");
Node vier = new Node(4);
HeapElement he2=new HeapElement(vier,5);
System.out.println(he2+"\n");
System.out.println("Einfü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ü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);
}
*/
}
|