heap/ ├ Heap.java └ Main.java
$ javac Heap.java
$ javac Main.java
$ java Main
Heap.java
import java.util.*;
/**
*Classe pour le tri de tas
*/
public class Heap {
int[] origArray;
int[] origHeap;
int[] forSortHeap;
int[] sortedHeap;
int arrayLength;
/**
*Obtenez un tableau pour le tri du tas.
*/
public void getForSortHeap(){
for (int i: forSortHeap){
System.out.print(i+", ");
}
System.out.println();
}
/**
*Obtenez un tableau trié par tas
*/
public void getSortedHeap(){
for (int i: sortedHeap){
System.out.print(i+", ");
}
System.out.println();
}
/**
*constructeur. Stocker les données du tableau dans le tableau de tas
* @tableau de paramètres Tableau initial avant le tri
*/
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);
}
}
/**
*Stocker l'élément idxNth dans le tableau de tas
* @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;
}
}
/**
*Effectuez un tri de tas (supprimez le tas maximum du tableau de tas et ajoutez-le au tableau dans l'ordre)
*/
public void sort(){
for (int i = 0; i < arrayLength; i++){
sortedHeap[i] = getMax();
removeMax(i);
}
}
/**
*Pop la valeur maximale dans le tas et la re-stocker dans un nouveau tableau pour le tas
* @idx du paramètre idxNmax pour 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;
}
}
}
/**
*Obtenez le tas maximum
* @renvoie la valeur maximale
*/
public int getMax(){
return forSortHeap[0];
}
/**
*Échangez les éléments du tableau
* @param arr swap matrice cible
* @param a index 1er
* @param b index 2ème
*/
public void swap(int[] arr, int a, int b){
int tmp = 0;
tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
Classe d'exécution
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