基本ヒープソート
一、概念とその紹介
ヒープソート(Heapsort)は、ヒープというデータ構造を利用して設計されたソートアルゴリズムです。
ヒープは、ほぼ完全二分木の構造であり、同時にヒープの性質を満たします:すなわち、子ノードのキー値またはインデックスは、常にその親ノードより小さい(または大きい)ことです。
二、適用説明
以前のヒープ構築プロセスは、データごとに insert メソッドを呼び出し、shift up を使用して一つずつヒープに挿入するというものでした。このアルゴリズムの時間計算量はO(nlogn)、本節で紹介するヒープソートを構築するプロセスは、と呼ばれますHeapify、アルゴリズムの時間計算量はO(n)。
三、プロセス図示
完全二分木には重要な性質があります。最初の非葉ノードのインデックスはn/2整数として取得したインデックス値です。ここでnは要素数です(前提として、配列インデックスは 1 から始まるものとします)。

インデックス 5 の位置が最初の非葉ノードです。そこから前へ順に、各要素をそれぞれルートノードとして shift down 操作を行い、最大ヒープの性質を満たします。
インデックス 5 の位置で shift down 操作を行った後、22 と 62 の位置を交換します。

インデックス 4 の要素に対して shift down 操作を行います

インデックス 3 の要素に対して shift down 操作を行います

インデックス 2 の要素に対して shift down 操作を行います

最後にルートノードに対して shift down 操作を行うと、ヒープソートのプロセス全体が完了します。

四、Java サンプルコード
ソースコードパッケージのダウンロード:Download
src/サンプル/heap/Heapify.java ファイルのコード:
package サンプル.heap;
import サンプル.sort.SortTestHelper;
/**
* heapify を使用してヒープソートを行う
*/
public class Heapify<T extends Comparable> {
protected T[] data;
protected int count;
protected int capacity;
// コンストラクタ。与えられた配列から最大ヒープを作成します
// このヒープ構築プロセスの時間計算量は O(n) です
public Heapify(T arr[]){
int n = arr.length;
data = (T[])new Comparable[n+1];
capacity = n;
for( int i = 0 ; i < n ; i ++ )
data[i+1] = arr[i];
count = n;
// 最初の非葉ノードの要素から開始します
for( int i = count/2 ; i >= 1 ; i -- )
shiftDown(i);
}
// ヒープ内の要素数を返します
public int size(){
return count;
}
// ヒープが空かどうかを示すブール値を返します
public boolean isEmpty(){
return count == 0;
}
// 最大ヒープに新しい要素 item を挿入します
public void insert(T item){
assert count + 1 <= capacity;
data[count+1] = item;
count ++;
shiftUp(count);
}
// 最大ヒープからヒープの先頭要素を取り出します。つまり、ヒープに格納されている最大データです
public T extractMax(){
assert count > 0;
T ret = data[1];
swap( 1 , count );
count --;
shiftDown(1);
return ret;
}
// 最大ヒープの先頭要素を取得します
public T getMax(){
assert( count > 0 );
return data[1];
}
// ヒープ内のインデックス i と j の2つの要素を交換します
private void swap(int i, int j){
T t = data[i];
data[i] = data[j];
data[j] = t;
}
//********************
//* 最大ヒープの中核となる補助関数
//********************
private void shiftUp(int k){
while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
swap(k, k/2);
k /= 2;
}
}
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k; // このループでは、data[k] と data[j] が位置を交換します
if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
j ++;
// data[j] は data[2*k] と data[2*k+1] のうちの最大値です
if( data[k].compareTo(data[j]) >= 0 ) break;
swap(k, j);
k = j;
}
}
// heapify をテストします
public static void main(String[] args) {
int N = 100;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
Heapify<Integer> heapify = new Heapify<Integer>(arr);
// heapify 内のデータを extractMax を使用して徐々に取り出します
// 取り出される順序は、大きい順(降順)でなければなりません
for( int i = 0 ; i < N ; i ++ ){
arr[i] = heapify.extractMax();
System.out.print(arr[i] + " ");
}
// arr 配列が降順(大きい順)に並んでいることを確認します
for( int i = 1 ; i < N ; i ++ )
assert arr[i-1] >= arr[i];
}
}
import サンプル.sort.SortTestHelper;
/**
* heapify を使用してヒープソートを行う
*/
public class Heapify<T extends Comparable> {
protected T[] data;
protected int count;
protected int capacity;
// コンストラクタ。与えられた配列から最大ヒープを作成します
// このヒープ構築プロセスの時間計算量は O(n) です
public Heapify(T arr[]){
int n = arr.length;
data = (T[])new Comparable[n+1];
capacity = n;
for( int i = 0 ; i < n ; i ++ )
data[i+1] = arr[i];
count = n;
// 最初の非葉ノードの要素から開始します
for( int i = count/2 ; i >= 1 ; i -- )
shiftDown(i);
}
// ヒープ内の要素数を返します
public int size(){
return count;
}
// ヒープが空かどうかを示すブール値を返します
public boolean isEmpty(){
return count == 0;
}
// 最大ヒープに新しい要素 item を挿入します
public void insert(T item){
assert count + 1 <= capacity;
data[count+1] = item;
count ++;
shiftUp(count);
}
// 最大ヒープからヒープの先頭要素を取り出します。つまり、ヒープに格納されている最大データです
public T extractMax(){
assert count > 0;
T ret = data[1];
swap( 1 , count );
count --;
shiftDown(1);
return ret;
}
// 最大ヒープの先頭要素を取得します
public T getMax(){
assert( count > 0 );
return data[1];
}
// ヒープ内のインデックス i と j の2つの要素を交換します
private void swap(int i, int j){
T t = data[i];
data[i] = data[j];
data[j] = t;
}
//********************
//* 最大ヒープの中核となる補助関数
//********************
private void shiftUp(int k){
while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
swap(k, k/2);
k /= 2;
}
}
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k; // このループでは、data[k] と data[j] が位置を交換します
if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
j ++;
// data[j] は data[2*k] と data[2*k+1] のうちの最大値です
if( data[k].compareTo(data[j]) >= 0 ) break;
swap(k, j);
k = j;
}
}
// heapify をテストします
public static void main(String[] args) {
int N = 100;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
Heapify<Integer> heapify = new Heapify<Integer>(arr);
// heapify 内のデータを extractMax を使用して徐々に取り出します
// 取り出される順序は、大きい順(降順)でなければなりません
for( int i = 0 ; i < N ; i ++ ){
arr[i] = heapify.extractMax();
System.out.print(arr[i] + " ");
}
// arr 配列が降順(大きい順)に並んでいることを確認します
for( int i = 1 ; i < N ; i ++ )
assert arr[i-1] >= arr[i];
}
}