/* ヒープソート */
import java.util.*;
class HeapSort {
    public static void main (String[] args) {
        int   seed = 3885;                   // 擬似乱数の種
        int   size = 1000;                   // 配列の大きさ
        int[] data = make_array(size, seed); // 配列データを作成

    	heap_sort(data);      	      	     // 配列データをクイックソート
        print_array(data);                   // ソート結果を表示
        if (!is_sorted_array(data)) {        // ソート結果をチェック
            System.out.println("bad sorted");
        }
    }

    // 配列中の2つのデータ data[i]と data[j]の値を交換する．
    static void swap (int[] data, int i, int j) {
        int tmp=data[i]; data[i]=data[j]; data[j]=tmp;
    }

    // 整数の大きさ sizeの配列をつくり，種を seedとした
    // 擬似乱数で初期化する．種が同じならば同じデータ列となる．
    // この配列をソートするデータ列として使用する．
    // sizeで割った余りとしているのは，重複データを作るためである．
    static int[] make_array (int size, long seed) {
        Random random = new Random(seed);
        int[]  data = new int[size];

        for (int i=0; i<data.length; i++) {
            // 0〜size-1 の範囲でランダムにデータを生成
            data[i] = Math.abs(random.nextInt()) % size;
        }
        return data;
    }

    // 整数配列の中身を表示するメソッド．ソートの様子を知るのに便利．
    static void print_array (int[] data) {
        for (int i=0; i<data.length; i++) {
            System.out.print(data[i]+" ");
        }
        System.out.println(); // 改行する
    }

    // 整数配列 dataが昇順ならば true，さもなくば falseを返すメソッド．
    // データ数が多い時に，ソート結果をチェックするのに便利．
    static boolean is_sorted_array(int[] data) {
        for (int i=0; i<data.length-1; i++) {
            if (data[i]>data[i+1]) {
                return false;
            }
        }
        return true;
    }

    static void heap_sort (int[] data) {
	/* 0〜(i-1)までがヒープ化済み．i番目のデータをヒープに挿入する */
	for (int i=1; i<data.length; i++) {
	    heap_insert(data, i);
	}
	/* ヒープから1つずつデータを取り出す．大きい順に出てくる．*/
	for (int i=data.length-1; i>0; i--) {
	    swap(data, 0, i);     // 最大要素 data[0] をdata[i]と交換
	    downheap(data, 0, i-1); // 残りの（壊れた）ヒープを修復する
	}
    }

    /* ヒープ（data[0]〜data[n-1]）にデータdata[n]を挿入する */
    static void heap_insert (int[] data, int n) {
	// 親が子より小さいか，根に到達するまで繰り返す．
	for (int i=n; i>0 && data[i]>data[parent(i)]; i=parent(i)) {
	    swap(data, i, parent(i)); // 親子で入れ換え
	}
    }

    /* ヒープ中の根ノードfromのみの不整合を解消する．*/
    static void downheap (int[] data, int from, int to) {
	for (int i=from, j; left(i)<=to; i=j) {
	    j=left(i); 
	    if (right(i)<=to && data[left(i)]<=data[right(i)]) {
		j=right(i);
	    } // ここまでで2つの子の小さい方がdata[j]になっている
	    if (data[j]>data[i]) {  // 子の小さい方が親より大きければ
		swap(data, i, j);   // 交換する
	    } else {
		return;             // 交換しなければ終了
	    }
	}
    }

    static int left   (int i) { return 2*i+1; }   // 左の子のインデックス
    static int right  (int i) { return 2*i+2; }   // 右の子のインデックス
    static int parent (int i) { return (i-1)/2; } // 親のインデックス
}

/*
    付記: s4-2-1.java から s4-2-5.java まで共通部分が何度も
          でてくるが，本当は1つにまとめた方が好ましい．
*/