DaryHeap.java
DaryHeap.java
— 6.7 KB
Dateiinhalt
import java.util.ArrayList;
import java.util.List;
/**
* Diese Klasse implementiert die Datenstruktur d-närer Min-Heap als heapgeordnetes Array.
*
* @param <T>
* Klasse der Objekte, die im d-nären Min-Heap abgelegt werden sollen
*/
public class DaryHeap<T extends Comparable<T>> {
// das heapgeordnete Array, in dem die Elemente des Heaps gespeichert werden
private List<T> elements;
// die Obergrenze für die Anzahl der Kinder eines Elements des Heaps
private final int d;
public DaryHeap(int d) {
this.elements = new ArrayList<>();
this.d = d;
}
/**
* Hilfsmethode zum Tauschen zweier Elemente mit Indizes i und j im heapgeordneten Array.
*
* @param i
* Index des ersten zu tauschenden Elements im heapgeordneten Array
* @param j
* Index des zweiten zu tauschenden Elements im heapgeordneten Array
*/
protected void swap(int i, int j) {
T elementI = elements.get(i);
T elementJ = elements.get(j);
elements.set(j, elementI);
elements.set(i, elementJ);
}
/**
* Hilfsmethode zum "Heruntersickern" des Elements mit Index i im heapgeordneten Array.
*
* @param i
* Index des Elements, das im heapgeordneten Array heruntersickern soll
*/
protected void siftDown(int i) {
// zunächst wird das aktuelle Element (Index i) mit all seinen Kindern verglichen und das kleinste Element wird ermittelt
int smallest = i;
for (int pos = 1; pos <= d; pos++) {
int child = d * i + pos;
if (child < size() && elements.get(child).compareTo(elements.get(smallest)) < 0) {
smallest = child;
}
}
// wenn das kleinste ermittelte Element ein Kind ist, dann wird mit ihm getauscht und von dort weiter heruntergesickert
if (smallest != i) {
swap(i, smallest);
siftDown(smallest);
}
}
/**
* Methode zum Ausgeben und Löschen des kleinsten Elements (also des Wurzelelements) im heapgeordneten Array.
*
* @return das kleinste Element (also das Wurzelelement) des heapgeordneten Array
*/
public T deleteMin() {
// Das Wurzelelement wird ermittelt, mit dem letzten Element vertauscht und gelösscht
if (this.size() == 0) {
return null;
}
T min = this.elements.get(0);
int n = this.size();
swap(0, n - 1);
this.elements.remove(n - 1);
// anschließend sickert das neue Wurzelelement herunter und das alte Wurzelelement wird zurückgegeben
siftDown(0);
return min;
}
/**
* Methode zum Erstellen eines neuen heapgeordneten Arrays aus einer übergebenen Liste.
*
* @param list
* Liste von Elementen, aus der ein neues heapgeordnetes Array erstellt werden soll
*/
public void build(List<T> list) {
// TODO Von den Studenten zu implementieren
}
/**
* Hilfsmethode zum "Hochsickern" des Elements mit Index i im heapgeordneten Array.
*
* @param i
* Index des Elements, das im heapgeordneten Array hochsickern soll
*/
protected void siftUp(int i) {
// TODO Von den Studenten zu implementieren
}
/**
* Methode zum Hinzufügen des neuen Element element zum heapgeordneten Array.
*
* @param element
* das neu hinzuzufügende Element
*/
public void add(T element) {
// TODO Von den Studenten zu implementieren
}
/**
* Methode zum Ermitteln aller Elemente im heapgeordneten Array, die kleiner als ein übergebenes Element sind.
*
* @param element
* das Element, das mit Elementen im heapgeordneten Array verglichen werden soll
* @return Elemente im heapgeordneten Array, die kleiner als das übergebene Element sind
*/
public List<T> smallerAs(T element) {
// TODO Von den Studenten zu implementieren
List<T> elementsSmaller = new ArrayList<>();
return elementsSmaller;
}
/**
* Hilfsmethode, die überprüft, ob die Heap-Eigenschaft erfüllt ist.
*/
protected void check() {
for (int i = 0; i < size(); i++) {
for (int pos = 1; pos <= d; pos++) {
int offset = d * i + pos;
if (offset < size() && elements.get(i).compareTo(elements.get(offset)) > 0) {
System.err.println("Min-Heap-Error. Vater-Knoten " + elements.get(i) + " ist kleiner als sein Kind " + elements.get(offset));
}
}
}
}
@Override
public String toString() {
return this.elements.toString();
}
/**
* Methode, die die Größe des heapgeordneten Arrays ausgibt.
*
* @return die Größe des heapgeordneten Arrays
*/
public int size() {
return elements.size();
}
/**
* Methode, die ausgibt, ob das heapgeordnete Array leer ist.
*
* @return true, gdw das heapgeordnete Array leer ist.
*/
public boolean isEmpty() {
return elements.isEmpty();
}
public static void main(String[] argv) {
// Generiere eine Liste der Zahlen von 30 bis 21 und 1 bis 10
List<Integer> list = new ArrayList<>();
for (int i = 30; i > 20; i--) {
list.add(i);
}
for (int i = 1; i <= 10; i++) {
list.add(i);
}
System.out.println("Erstelle Liste: " + list.toString());
// Erstelle daraus einen 4-nären Min-Heap
DaryHeap<Integer> minHeap = new DaryHeap<>(4);
minHeap.build(list);
// Prüfe, ob der Min-Heap korrekt erstellt wurde.
minHeap.check();
System.out.println("Baue Heap aus Liste: " + minHeap.toString());
System.out.println("Er sollte so aussehen: [1, 22, 2, 4, 8, 25, 24, 23, 29, 21, 28, 30, 3, 27, 5, 6, 7, 26, 9, 10]");
System.out.println();
// Ermittle alle Elemente kleiner als 5 und kleiner als 10
List<Integer> smaller = minHeap.smallerAs(5);
System.out.println("Zahlen kleiner als 5: " + smaller);
smaller = minHeap.smallerAs(10);
System.out.println("Zahlen kleiner als 10: " + smaller);
System.out.println();
// Extrahiere zwei mal das Minimum aus dem Min-Heap
for (int i = 0; i < 2; i++) {
System.out.println("Extrahiere Minimum: " + minHeap.deleteMin());
}
// Prüfe, ob der Min-Heap noch korrekt ist.
minHeap.check();
System.out.println("Heap nach Extraktion: " + minHeap.toString());
System.out.println("Er sollte so aussehen: [3, 22, 9, 4, 8, 25, 24, 23, 29, 21, 28, 30, 10, 27, 5, 6, 7, 26]");
System.out.println();
// Füge die Zahlen von 11 bis 20 zum Min-Heap hinzu
for (int i = 11; i <= 20; i++) {
minHeap.add(i);
}
// Prüfe, ob der Min-Heap noch korrekt ist.
minHeap.check();
System.out.println("Füge 11 bis 20 hinzu: " + minHeap.toString());
System.out.println("Er sollte so aussehen: [3, 14, 9, 4, 8, 15, 18, 23, 29, 21, 28, 30, 10, 27, 5, 6, 7, 26, 11, 12, 13, 25, 22, 16, 17, 24, 19, 20]");
System.out.println();
System.out.println("Extrahiere alle Werte.");
int lastMin = Integer.MIN_VALUE;
while (!minHeap.isEmpty()) {
minHeap.check();
int min = minHeap.deleteMin();
if (min < lastMin) {
System.out.println("Minimum nicht korrekt: " + min + "<" + lastMin);
} else {
System.out.print(".");
}
lastMin = min;
}
System.out.println("\n");
}
}