ディレクトリ構造
heap/
├ Heap.java
└ Main.java
実行
$ javac Heap.java
$ javac Main.java
$ java Main
ソースコード
Heap.java
import java.util.*;
/**
* ヒープソート用のクラス
*/
public class Heap {
int[] origArray;
int[] origHeap;
int[] forSortHeap;
int[] sortedHeap;
int arrayLength;
/**
* ヒープソート用の配列を取得する．
*/
public void getForSortHeap(){
for (int i: forSortHeap){
System.out.print(i+", ");
}
System.out.println();
}
/**
* ヒープソートされた配列を取得する
*/
public void getSortedHeap(){
for (int i: sortedHeap){
System.out.print(i+", ");
}
System.out.println();
}
/**
* コンストラクタ．配列データをヒープ配列に格納する
* @param array ソート前の初期配列
*/
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);
}
}
/**
* idxN番目の要素をヒープ配列に格納する
* @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;
}
}
/**
* ヒープソートを実行（ヒープの最大値をヒープ配列から削除して，順に配列に追加する）
*/
public void sort(){
for (int i = 0; i < arrayLength; i++){
sortedHeap[i] = getMax();
removeMax(i);
}
}
/**
* ヒープ内の最大値をpopし，ヒープ用の新しい配列に再格納
* @param idxNmax forSortHeapのidx (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;
}
}
}
/**
* ヒープの最大値を取得
* @return 最大値
*/
public int getMax(){
return forSortHeap[0];
}
/**
* 配列の要素の入れ替えを行う
* @param arr swap対象の配列
* @param a index 1つ目
* @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;
}
}
実行用クラス
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,