O(N*log(N))のSorting Algorithm - Heap Sort(整列2分木法)

http://d.hatena.ne.jp/yokolet/20080628#1214690163で、計算量の話をしたのですが、"Sorting"に、O(N^2)とO(N*logn(N))のsorting algorithmsの比較の図が掲載されていました。この図を見ると、入力データ数が大きくなると、明らかにO(N*log(N))で済む方が速いことがわかります。O(N*log(N))の計算量で済むsortingのひとつ、Heap Sort(整列2分木法)について調べてみたので忘れないようにメモです。
Heap Sortというのはheapと呼ばれるデータ構造を利用するソート法です。このデータ構造は与えられた入力値を2分木にマッピングしていきますが、ツリーのどの場所でも、親の要素は2つの子の要素よりも常に小さい(または大きい)状態を保っている木です。つまり、root(根)の部分には必ず最小値(または最大値)がくるようになっています。例えば、16, 1, 9, 6, 10, 2, 11, 8, 4, 5という数字をheapで表現すると

        1
     /     \
   4        2
  /  \     /  \
 6    5   9    11
/ \   |
8 16  10

のようになります。このようなheapを表現するのに使われるのがPriority Queueと呼ばれる配列です。このheapの場合、

[1, 4, 2, 6, 5, 9, 10, 8, 16, 10]

というように、ツリーのroot、一段下がって左から右へ、さらに一段下がって左から右へと並べて配列を作るとPriority Queueになります。
Heap sortを行うには、heapのroot nodeを削除して、代わりにthe deepest & rightmost node(最も下の最も右)をroot nodeに置いたのち、各要素を比較してheapを作り直す操作を再帰的に実行します。

初期状態
        1   
     /     \   
   4        2   
  /  \     /  \    priority queue
 6    5   9    11  [1, 4, 2, 6, 5, 9, 10, 8, 16, 10] 
/ \   |   
8 16  10  


root nodeを取り出して、the deepest,rightmostをroot nodeに置いた状態
        10  
     /     \   
   4        2   
  /  \     /  \
 6    5   9    11  
/ \   
8 16


最上段の親と２つの子の要素を比較して並べ替えた状態
        2   
     /     \   
   4        10  
  /  \     /  \
 6    5   9    11  
/ \   
8 16


並べ替えが終わった状態
        2   
     /     \   
   4        9   
  /  \     /  \     priority queue
 6    5   10    11  [2, 4, 9, 6, 5, 10, 11, 8, 16]
/ \
8 16

次のステップでは2を削除して16をrootに持ってきて、heapを作り直す。

この作業を繰り返すと、常に最小値(または最大値)をツリー構造から取り出すことになるので、取り出した値をその順番で並べればソートが出来上がるというものです。

Javaでは1.5でjava.util.PriorityQueueが追加されたので、このクラスを使ってHeap Sortを行ってみました。

import java.util.ArrayList;
import java.util.Iterator;
import java.util.PriorityQueue;

public class HeapSort {
    private ArrayList sortedList = new ArrayList();

    private HeapSort() {
        ArrayList inputList = new ArrayList();
        int inputs = {16, 1, 9, 6, 10, 2, 11, 8, 4, 5};
        for (int input : inputs) {
            inputList.add(input);
        }
        PriorityQueue queue = new PriorityQueue(inputList);
        sort(queue);
        System.out.println(sortedList);
    }
    
    private void sort(PriorityQueue queue) {
        print(queue);
        Integer value = (Integer)queue.poll();
        if (value != null) {
            sortedList.add(value);
            sort(queue);
        }
    }
    
    private void print(PriorityQueue q) {
        Iterator iterator = q.iterator();
        while(iterator.hasNext()) {
            System.out.print(iterator.next() + "|");
        }
        System.out.println();
    }
    
    public static void main(String args) {
        new HeapSort();
    }
}

実行結果
1|4|2|6|5|9|11|8|16|10|
2|4|9|6|5|10|11|8|16|
4|5|9|6|16|10|11|8|
5|6|9|8|16|10|11|
6|8|9|11|16|10|
8|10|9|11|16|
9|10|16|11|
10|11|16|
11|16|
16|

[1, 2, 4, 5, 6, 8, 9, 10, 11, 16]

というようにheapのroot nodeやそれ以下のツリー構造が順番に入れ替わってソートされていく様子がわかります。計算量は2分木を使っているので、1/2*1/2...のところからO(log(N))、要素を比較して入れ替えるところは線形なのでO(N)、全体でO(N*log(N))になるというものです。

なお、 java.util.PriorityQueueはComparatorを指定すれば文字列を比較してsortingする用途にも使えます。