heap/ ├ Heap.java └ Main.java
$ javac Heap.java
$ javac Main.java
$ java Main
Heap.java
import java.util.*;
/**
*Klasse für die Heap-Sortierung
*/
public class Heap {
int[] origArray;
int[] origHeap;
int[] forSortHeap;
int[] sortedHeap;
int arrayLength;
/**
*Holen Sie sich ein Array für die Heap-Sortierung.
*/
public void getForSortHeap(){
for (int i: forSortHeap){
System.out.print(i+", ");
}
System.out.println();
}
/**
*Holen Sie sich ein Heap-sortiertes Array
*/
public void getSortedHeap(){
for (int i: sortedHeap){
System.out.print(i+", ");
}
System.out.println();
}
/**
*Konstrukteur. Speichern Sie Array-Daten im Heap-Array
* @param array Erstes Array vor dem Sortieren
*/
public Heap(int[] array){
arrayLength = array.length;
this.origArray = new int[array.length];
this.origArray = array;
this.origHeap = new int[array.length];
this.forSortHeap = new int[array.length];
this.sortedHeap = new int[array.length];
for (int i = 0; i < array.length; i++){
insert(i);
}
}
/**
*Speichern Sie das idxNth-Element im Heap-Array
* @param idxN
*/
public void insert(int idxN){
int idxParent = idxN;
int nextIdxParent = 0;
int tmp = 0;
this.forSortHeap[idxN] = this.origArray[idxN];
while (idxParent >= 0){
nextIdxParent = idxParent / 2;
if (forSortHeap[nextIdxParent] < forSortHeap[idxParent]){
swap(forSortHeap, nextIdxParent, idxParent);
} else {
break;
}
idxParent = nextIdxParent;
}
}
/**
*Führen Sie die Heap-Sortierung aus (entfernen Sie den Maximalwert des Heaps aus dem Heap-Array und fügen Sie ihn der Reihe nach dem Array hinzu.)
*/
public void sort(){
for (int i = 0; i < arrayLength; i++){
sortedHeap[i] = getMax();
removeMax(i);
}
}
/**
*Fügen Sie den Maximalwert in den Heap ein und speichern Sie ihn in einem neuen Array für den Heap
* @idx von param idxNmax für SortHeap(n-th max value in array will be deleted. )
*/
public void removeMax(int idxNmax){ // n-th max value in array will be deleted.
int idxChild = 0;
forSortHeap[0] = forSortHeap[arrayLength - idxNmax - 1];
forSortHeap[arrayLength - idxNmax - 1] = 0;
while (2 * idxChild + 2 < arrayLength){
if ((forSortHeap[idxChild] > forSortHeap[2 * idxChild + 1]) && (forSortHeap[idxChild] > forSortHeap[2 * idxChild + 2])){
break;
}
if (forSortHeap[2 * idxChild + 1] >= forSortHeap[2 * idxChild + 2]){
swap(forSortHeap, 2 * idxChild + 1, idxChild);
idxChild = 2 * idxChild + 1;
} else {
swap(forSortHeap, 2 * idxChild + 2, idxChild);
idxChild = 2 * idxChild + 2;
}
}
}
/**
*Holen Sie sich maximalen Haufen
* @Maximalwert zurückgeben
*/
public int getMax(){
return forSortHeap[0];
}
/**
*Tauschen Sie die Elemente des Arrays aus
* @param arr Swap-Zielarray
* @param a index 1st
* @param b index 2 ..
*/
public void swap(int[] arr, int a, int b){
int tmp = 0;
tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
Ausführungsklasse
Main.java
import java.util.*;
public class Main {
public static void main(String[] args){
int[] a = {3,9,1,6,10,13,2,18,4,7,20};
Heap heap = new Heap(a);
System.out.println("getForSortHeap>>> ");
heap.getForSortHeap();
heap.sort();
System.out.println("getSortedHeap>>> ");
heap.getSortedHeap();
}
}
getForSortHeap>>>
20, 18, 13, 10, 7, 9, 2, 3, 1, 4, 6,
getSortedHeap>>>
20, 18, 13, 10, 9, 7, 6, 4, 3, 2, 1,
Recommended Posts