基本情報技術者の擬似言語の学習のため実際にプログラム化してみました。
仕様はそのままに一部アルゴリズム強化のため自分で自分で条件式等を考えているため実際の擬似言語プログラムとは差異があります。
qiita.java
import java.util.*;
public class HeapSort {
public static void main(String[] args) {
// 変数
Scanner sc = new Scanner(System.in);
System.out.println("配列の要素数を入力してください");
int n = Integer.parseInt(sc.next());
int data_array[] = new int[n]; // [20,50,10,30,70,40,60,80]
System.out.println("配列の各要素を" + n + "回入力してください");
for (int i = 0; i < n; i++) {
data_array[i] = Integer.parseInt(sc.next());
}
// ヒープ木の作成
for (int i = 1; i < data_array.length; i++) {
// ヒープ木の作成
makeHeap(i, data_array);
}
/*
* ヒープの昇順並び替え
* ヒープ木の再構築
*/
for (int i = data_array.length - 1; i > 0; i--) {
// 配列先頭要素と配列末尾の要素を入れ替え
swap(0, i, data_array);
// 並び替え範囲を狭めてヒープ木再構築
remakeHeap(i - 1, data_array);
}
// 並び替え終了
// 出力
resultPrint(data_array);
}
// ヒープ木の作成(一番大きい要素を先頭へ)
public static void makeHeap(int child, int[] data_array) {
while (child != 0) {
if (data_array[child] > data_array[parentIndex(child)]) {
// 入れ替え
swap(child, parentIndex(child), data_array);
// child更新 要素番号を返す
child = parentIndex(child);
} else {
child = 0;
}
}
}
// ヒープ木再構築 範囲内で一番大きいものをヒープ木の根とする。
public static void remakeHeap(int heap_range, int[] data_array) {
int data_array_parent_index = 0;
int tmp = 0;
// 左子が配列の範囲内にいるか
while (leftChildIndex(data_array_parent_index) <= heap_range) {
tmp = leftChildIndex(data_array_parent_index);
// 右子が配列の範囲内にいるか
if (rightChildIndex(data_array_parent_index) <= heap_range) {
// 左子の要素と右子の要素を比べる。大きい方を親と比較
if (data_array[tmp] < data_array[rightChildIndex(data_array_parent_index)]) {
tmp = rightChildIndex(data_array_parent_index);
}
}
// 親と子どもを比較
if (data_array[tmp] > data_array[data_array_parent_index]) {
swap(tmp, data_array_parent_index, data_array);
} else {
return;
// brakeならどうなる。
}
data_array_parent_index = tmp;
}
}
// 親と子供を入れ替える
public static void swap(int child, int parent, int[] data_array) {
int tmp = 0;
tmp = data_array[parent];
data_array[parent] = data_array[child];
data_array[child] = tmp;
}
// 親の添字を返す
public static int parentIndex(int num) {
if (num != 0) {
return (num - 1) / 2;
} else {
// ゼロ除算でエラー対策
return 0;
}
}
// 左子の添字を返す
public static int leftChildIndex(int left_index) {
return 2 * left_index + 1;
}
// 右子の添字を返す
public static int rightChildIndex(int right_index) {
return 2 * right_index + 2;
}
// プリントアウト
public static void resultPrint(int[] data_array) {
System.out.println("結果表示");
System.out.println(Arrays.toString(data_array));
}
}