Javaの最大ヒープ（Max Heap）とは？PriorityQueueを使った実装方法をわかりやすく解説

最大ヒープ（Max Heap）とは

最大ヒープは完全二分木の一種で、すべての親ノードの値が子ノードの値以上であるという性質を持つデータ構造です。この特性により、木の根（ルート）には常に最大の要素が配置されるため、優先度付きキューの実装などに広く活用されています。

Javaでは、標準ライブラリの java.util.PriorityQueue クラスに Collections.reverseOrder() を組み合わせるだけで、最大ヒープを簡単に実現できます。通常の PriorityQueue は最小ヒープとして動作しますが、逆順のコンパレータを渡すことで、最大値が常に先頭に来る構造に変更できるのです。

PriorityQueueを使った最大ヒープの実装例

以下は、ライブラリ関数を使用して最大ヒープを実装したサンプルコードです。

import java.util.*;
public class Demo{
    public static void main(String args[]){
        PriorityQueue<Integer> my_p_queue = new PriorityQueue<Integer>(Collections.reverseOrder());
        my_p_queue.add(43);
        my_p_queue.add(56);
        my_p_queue.add(99);
        System.out.println("優先度付きキューの要素 :");
        Iterator my_iter = my_p_queue.iterator();
        while (my_iter.hasNext())
            System.out.println(my_iter.next());
        my_p_queue.poll();
        System.out.println("poll関数で要素を削除した後のキューの要素 :");
        Iterator<Integer> my_iter_2 = my_p_queue.iterator();
        while (my_iter_2.hasNext())
            System.out.println(my_iter_2.next());
        Object[] my_arr = my_p_queue.toArray();
        System.out.println("最大ヒープの配列表現 :");
        for (int i = 0; i < my_arr.length; i++)
            System.out.println("値: " + my_arr[i].toString());
    }
}

実行結果

優先度付きキューの要素 :
99
43
56
poll関数で要素を削除した後のキューの要素 :
56
43
最大ヒープの配列表現 :
値: 56
値: 43

コードの解説

Demo という名前のクラスには main メソッドが含まれています。main メソッド内では、まず Collections.reverseOrder() を引数に渡して PriorityQueue のインスタンスを生成し、add メソッドを使って 43、56、99 の3つの要素を追加しています。

次にイテレータを定義し、優先度付きキュー内の要素を順番に走査して表示します。ここで最初の要素として 99（最大値）が出力される点に注目してください。続いて poll メソッドを呼び出すと、キューの先頭にある最大値が削除されます。その後、残りの要素を再度走査して画面に表示し、最後に toArray メソッドでヒープの内容を配列形式に変換して出力しています。

補足：計算量と注意点

• 要素の追加（add）や削除（poll）は、ヒープの再構築が必要となるため、計算量は O(log n) です。
• イテレータによる走査順序は、必ずしも降順にソートされた順序になるとは限りません。常に最大値を取得したい場合は peek や poll を使用しましょう。
• toArray メソッドを使うことで、ヒープ内部の状態を配列として確認でき、デバッグにも役立ちます。