Java で最小-最大ヒープを実装する

1. Java での最小-最大ヒープの概要
2. Java で PriorityQueue クラスと Collections.reverseOrder() を使用して Max-Heap を実装する
3. Java で PriorityQueue クラスを使用して最小ヒープを実装する

この記事では、PriorityQueue クラスを使用して最大ヒープと最小ヒープを実装します。また、ヒープからの要素の挿入と削除についても説明します。

Java での最小-最大ヒープの概要

ヒープはツリーに基づくデータ構造であり、完全な二分木を形成します。ヒープは配列として表されます。ヒープには、最小ヒープと最大ヒープの 2 種類があります。最小ヒープは、最小ヒープとも呼ばれ、ルートノードまたは親ノードで最小値を持ちます。同様に、max-heap は、ルートノードまたは親ノードで最大の値を持ちます。したがって、ヒープデータ構造により、配列から最大要素と最小要素を簡単に抽出できます。O(1) で最大要素と最小要素を取得できます。ヒープへの要素の削除またはヒープからの要素の挿入の複雑さは、O(log N) です。

最小-最大ヒープは、最小レベルと最大レベルが交互に含まれるデータ構造です。ルートノードには最小値が含まれ、その下の次のレベルは最大値を表します。最小値は 0、2、4 のような偶数レベルで表されます。1、3、5 のような奇数レベルは最大値を表します。

Java で PriorityQueue クラスと Collections.reverseOrder() を使用して Max-Heap を実装する

PriorityQueue クラスを使用して、Java でヒープを実装できます。クラスはデフォルトで最小ヒープを実装し、Collections の reverseOrder() メソッドを使用して最大ヒープを実装できます。peek() メソッドを使用して、ルートノードの要素をヒープに表示できます。poll() メソッドは、ルートノードの値を返したり削除したりします。contains() メソッドを使用して、要素がヒープに存在するかどうかを確認できます。

たとえば、java.util パッケージからすべてをインポートします。クラス MaxHeap を作成し、main メソッドを記述します。次に、PriorityQueue クラスのインスタンスを pq として作成します。ジェネリック型を使用して、Integer インスタンスを作成します。オブジェクトの作成中に、括弧内に Collections.reverseOrder() を記述します。add() メソッドを使用して、4つの整数値を追加します。オブジェクト pq を指定して peek() メソッドを呼び出し、それを出力します。次に、オブジェクトで poll() メソッドを使用します。次に、パラメータとして値 30 を指定して remove() メソッドを呼び出し、iterator() および hasNext() メソッドを使用して配列内の要素を出力します。最後に、パラメータ 20 を指定して contains() メソッドを使用します。

以下の例では、import java.util.*は、max-heap の作成に使用した PriorityQueue クラスをインポートします。ヒープに値 1、2、3、および 4 を追加しました。peek() メソッドは、ヒープ内で最大の値 4 を返しました。次に、poll() メソッドは最大数 4 を削除しました。次に、remove() メソッドを使用して数値 3 を削除し、残りの要素をヒープに出力しました。すでに 3 と 4 を削除したので、値 1 と 2 が出力されました。最後に、contains() メソッドを使用して、ヒープに数値 2 が含まれているかどうかを確認しました。ヒープ内に数値が存在するため、true が返されました。したがって、Collectios.reverseOrder() を使用して PriorityQueue クラスを使用して最大ヒープを実装しました。

サンプルコード：

import java.util.*;

class MaxHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr3.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(2);
    System.out.println("Does the heap contains 2 ?" + b);
  }
}

出力：

The highest value in the heap:4
after removing 3:
2
1
Does the heap contains 2 ?true

Java で PriorityQueue クラスを使用して最小ヒープを実装する

PriorityQueue クラスは、デフォルトで最小ヒープを実装します。最大ヒープの場合と同じ実装方法を最小ヒープに適用します。peek()、remove()、poll()、contains() などの同じメソッドを使用して、同じ操作を実行します。

以下の例では、ヒープに 1、2、3、および 4 の番号を追加しました。peek() メソッドは、出力に示されているように 1 であるルートノードの要素を返しました。poll() メソッドを使用して、ルートノード要素 1 を削除しました。remove() 関数を使用して、ヒープから値 3 を再度削除しました。これらの値を削除した後、ヒープには要素 2 と 4 のみが含まれます。最後に、contains() メソッドを使用して、ヒープ内の 3 を評価するかどうかを確認しました。すでに削除しているので、メソッドは false 値を返します。したがって、PriorityQueue クラスを使用して最小ヒープを実装しました。

コード例：

import java.util.*;

class MinHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(3);
    System.out.println("Does the heap contains 3 ?" + b);
  }
}

出力：

The highest value in the heap:1
after removing 3:
2
4
Does the heap contains 2 ?false