ヒープソート | アルゴリズム [AOJ 10029][Java]


今回は、『AOJ 10029 - ソートアルゴリズム』を非ヒープソートを使って解いてみました。Javaのサンプルソースを載せています。

algorithm-heap-sort

😸 ヒープとは?

  • ヒープとは親が子の値以上であるという条件を満たす完全2分木
  • 子をもつノードの値は、2つの子のどちらの値よりも大きい (逆でも可)

🎉 特徴

  • チャンピオンシップ・トーナメントの振る舞い
  • 単純選択ソートの応用的アルゴリズム
  • クイックソートの苦手な入力に対しても期待どおりの性能を発揮する
  • 平均時性能はクイックソートに負ける

😀 親インデックスと子インデックスの関係

  • 要素 a[i] に対して:
    • 親は a[(i-1)/2] (余剰は切り捨て)
    • 左の子は、a[i*2+1]
    • 右の子は、a[i*2+2]

🚌 AOJ問題

AOJ 10029 - ソートアルゴリズム

🍄 Javaコード

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
public static void main(String[] a) throws Exception {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(r.readLine());
String[] str = r.readLine().split(" ");

int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(str[i]);
}

arr = buildHeap(arr);

int tmp;
for (int i = n - 1; i >= 1; i--) {
tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
heapify(arr, 0, i);
}

StringBuilder s = new StringBuilder();
for (int i = 0; i < n; i++) {
s.append(arr[i]);
if (i != n - 1) {
s.append(" ");
}
}
System.out.println(s);
}

private static int[] buildHeap(int[] arr) {
int[] result = new int[arr.length];
for (int i = arr.length/2 - 1; i >= 0; i--) {
result = heapify(arr, i, arr.length);
}
return result;
}

private static int[] heapify(int[] arr, int index, int maxIndex) {
int leftIndex = 2 * index + 1;
int rightIndex = 2 * index + 2;

int largestIndex = index;
if (leftIndex < maxIndex && arr[leftIndex] > arr[index]) {
largestIndex = leftIndex;
}

if (rightIndex < maxIndex && arr[rightIndex] > arr[largestIndex]) {
largestIndex = rightIndex;
}

if (largestIndex != index) {
int tmp = arr[index];
arr[index] = arr[largestIndex];
arr[largestIndex] = tmp;
heapify(arr, largestIndex, maxIndex);
}

return arr;
}
}

🖥 VULTRおすすめ

VULTR」はVPSサーバのサービスです。日本にリージョンがあり、最安は512MBで2.5ドル/月($0.004/時間)で借りることができます。4GBメモリでも月20ドルです。 最近はVULTRのヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります!

📚 おすすめの書籍