Heap Sort
Implementierung
package net.bitelligence.training.exercise.sorting.heap_sort.specification;
public class HeapSort {
public int[] heapSort(int[] numbers) {
// ...
return numbers;
}
}package net.bitelligence.exercise.sorting;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
import net.bitelligence.exercise.sorting.HeapSort;
public class HeapSortTest {
@Test
public void should_correctly_sort_mixed_arrays() {
int[] unsorted1 = {};
int[] unsorted2 = { 1 };
int[] unsorted3 = { 2, 1 };
int[] unsorted4 = { 2, 1, 3 };
int[] unsorted5 = { 2, 4, 1, 3 };
int[] unsorted6 = { 2, 1, 2, 3, 9 };
int[] unsorted7 = { 1, 2, 3, 4, 5, 6 };
int[] expected1 = {};
int[] expected2 = { 1 };
int[] expected3 = { 1, 2 };
int[] expected4 = { 1, 2, 3 };
int[] expected5 = { 1, 2, 3, 4 };
int[] expected6 = { 1, 2, 2, 3, 9 };
int[] expected7 = { 1, 2, 3, 4, 5, 6 };
assertArrayEquals(expected1, new HeapSort().heapSort(unsorted1));
assertArrayEquals(expected2, new HeapSort().heapSort(unsorted2));
assertArrayEquals(expected3, new HeapSort().heapSort(unsorted3));
assertArrayEquals(expected4, new HeapSort().heapSort(unsorted4));
assertArrayEquals(expected5, new HeapSort().heapSort(unsorted5));
assertArrayEquals(expected6, new HeapSort().heapSort(unsorted6));
assertArrayEquals(expected7, new HeapSort().heapSort(unsorted7));
}
}package net.bitelligence.training.exercise.sorting.heap_sort.specification;
public class HeapSort {
public int[] heapSort(int[] numbers) {
// ...
return numbers;
}
}Funktionsweise
Hilfestellung
Tipp #1
Verstehen Sie die Grundidee des Algorithmus: Der Heap sort funktioniert, indem ein binärer Heap (ein spezieller Baum) aus dem Array erstellt wird. Der Wurzelknoten des Baums enthält das größte Element im Array. Durch das Entfernen des Wurzelknotens und Neubildung des Baums wird das nächstgrößte Element an die Wurzel gebracht. Das wiederholt sich bis das Array sortiert ist.
Tipp #2
Verstehen Sie den Unterschied zwischen Max-Heap und Min-Heap: Es gibt zwei Arten von Heaps, Max-Heap und Min-Heap. In einem Max-Heap ist der Wurzelknoten das größte Element im Baum, während es in einem Min-Heap das kleinste Element ist. Verstehen Sie welche Art von Heap für den Algorithmus verwendet werden sollte.
Tipp #3
Implementieren Sie die Heapify-Operation korrekt: Die Heapify-Operation ist der Prozess, bei dem ein ungeordneter Teil des Arrays in einen Heap umgewandelt wird. Stellen Sie sicher, dass die Heapify-Operation korrekt implementiert ist und das Array in einen Heap umgewandelt wird.
Optional
Verstehen Sie den Unterschied zwischen der In-Place und nicht-In-Place Implementierung. Es gibt zwei Arten von Heapsort, eine In-Place und eine nicht-In-Place Implementierung. Die In-Place Implementierung benötigt keinen zusätzlichen Speicherplatz während die nicht-In-Place Implementierung zusätzlichen Speicher benötigt. Verstehen Sie welche Art von Implementierung für Ihre Anforderungen am besten geeignet ist.
