Java で最小ヒープを実装する
最小ヒープは、各内部ノードがその子の値以下であるヒープです。以下のポイントで、ライブラリを使用する場合と使用しない場合の最小ヒープの実装方法を説明します。
Java でライブラリを使用せずに最小ヒープを実装する
この例では、ライブラリを使用しない実装を示しています。ここでは、3つのインスタンス変数を作成するクラス JavaMinHeap を作成します。HeapArray はヒープの全ての値を保持する int 型の配列であり、size はヒープのサイズであり、maxSize は HeapArray の最大サイズを格納します。また、タイプ int の static 変数 FRONT を作成し、1 で初期化します。
コンストラクターのパラメーターとして maxSize を取得し、インスタンス変数 maxSize に格納します。size を 0 で初期化し、HeapArray を maxSize + 1 のサイズの int の配列で初期化します。HeapArray の最初のインデックスに Integer の最小値を格納します。
次に、ヒープで操作を実行するメソッドを作成します。parent() 関数は、パラメーターとして position を取り、渡されたノードの位置の親を返します。次に、受け取った位置の左の子をパラメーターとして返す leftChild() を作成します。同じことが、(2 * position) + 1 ノードの値を返す rightChild() を使用する右の子にも当てはまります。
isLeaf() は、ノードがリーフノードであるかどうかをチェックします。これは、ノードに子があることを意味します。swapNodes() は、ノードの位置 fpos の値を位置 spos と交換するメソッドです。このメソッドでは、temp 変数を作成して初期化し、HeapArray の fpos 位置を初期化し、HeapArray の spos 値を HeapArray[fpos] に格納します。ここで、temp 値を HeapArray[spos] に格納します。
convertToMinHeap() は、パラメータとして受け取った位置がリーフであるかどうか、または isLeaf を使用していないかどうかをチェックし、そうでない場合は、HeapArray の位置の現在の値が左の子または右の子より大きいかどうかをチェックします。次に、左の子が右の子よりも小さいかどうかを確認し、小さい場合は、swapNodes() を使用してノードを交換し、position と左の子を position に渡します。受け取った左の子を、convertToMinHeap() を使用して最小ヒープに再度変換します。
insert() を使用して、最小ヒープに値を挿入します。insert() では、配列が maxSize に達した場合、挿入せずに戻ります。そうでない場合は、++size の位置を取得し、受け取った要素を HeapArray[++size] に挿入します。サイズを現在に置きます。現在の位置にある要素がその親よりも小さい場合は、ループを作成してノードを交換します。
最小ヒープを出力するには、printheap() を作成し、HeapArray をループします。ここで、親は ith の位置にあり、左の子は 2 * i の位置にあり、右の子は 2 * i + 1 の位置。main() 関数では、insert() を使用して要素をヒープに挿入します。
public class JavaMinHeap {
private final int[] HeapArray;
private int size;
private final int maxsize;
private static final int FRONT = 1;
public JavaMinHeap(int maxsize) {
this.maxsize = maxsize;
this.size = 0;
HeapArray = new int[this.maxsize + 1];
HeapArray[0] = Integer.MIN_VALUE;
}
private int parent(int position) {
return position / 2;
}
private int leftChild(int position) {
return (2 * position);
}
private int rightChild(int position) {
return (2 * position) + 1;
}
private boolean isLeaf(int position) {
if (position >= (size / 2) && position <= size) {
return true;
}
return false;
}
private void swapNodes(int fpos, int spos) {
int temp;
temp = HeapArray[fpos];
HeapArray[fpos] = HeapArray[spos];
HeapArray[spos] = temp;
}
private void convertToMinHeap(int position) {
if (!isLeaf(position)) {
if (HeapArray[position] > HeapArray[leftChild(position)]
|| HeapArray[position] > HeapArray[rightChild(position)]) {
if (HeapArray[leftChild(position)] < HeapArray[rightChild(position)]) {
swapNodes(position, leftChild(position));
convertToMinHeap(leftChild(position));
} else {
swapNodes(position, rightChild(position));
convertToMinHeap(rightChild(position));
}
}
}
}
public void insert(int element) {
if (size >= maxsize) {
return;
}
HeapArray[++size] = element;
int current = size;
while (HeapArray[current] < HeapArray[parent(current)]) {
swapNodes(current, parent(current));
current = parent(current);
}
}
public void printHeap() {
for (int i = 1; i <= size / 2; i++) {
System.out.println("PARENT : " + HeapArray[i]);
System.out.println("--LEFT CHILD : " + HeapArray[2 * i]);
System.out.println("--RIGHT CHILD : " + HeapArray[2 * i + 1]);
System.out.println();
}
}
public static void main(String[] arg) {
System.out.println("The Min Heap is ");
JavaMinHeap minHeap = new JavaMinHeap(10);
minHeap.insert(10);
minHeap.insert(2);
minHeap.insert(7);
minHeap.insert(15);
minHeap.insert(90);
minHeap.insert(19);
minHeap.insert(8);
minHeap.insert(22);
minHeap.insert(9);
minHeap.printHeap();
}
}
出力：
The Min Heap is
PARENT : 2
--LEFT CHILD : 9
--RIGHT CHILD : 7
PARENT : 9
--LEFT CHILD : 10
--RIGHT CHILD : 90
PARENT : 7
--LEFT CHILD : 19
--RIGHT CHILD : 8
PARENT : 10
--LEFT CHILD : 22
--RIGHT CHILD : 15
Java で PriorityQueue を使用した最小ヒープの実装
このプログラムでは、最大ヒープと最小ヒープを作成するために使用される PriorityQueue を使用します。PriorityQueue は、要素をキューに挿入する add() のような複数を提供します。peek() はキューの先頭をフェッチして削除します。poll() もキューの先頭を取得しますが、削除しません。contains() は、指定された要素がキューであることを確認します。remove() は、指定された要素を削除します。
PriorityQueue のすべての機能を組み合わせて、最小ヒープ操作を作成および実行します。まず、new PriorityQueue() を使用して、整数タイプの空の priorityQueue オブジェクトを作成します。次に、add() メソッドを使用して要素を追加します。キューヘッドを出力して削除するには、10 を出力する priorityQueue.peek() を呼び出します。次に、拡張された for を使用してキューのすべての要素を出力します。ここで、10 を出力して削除する poll() を呼び出します。次に、キューから要素を削除します。boolean を返す contains() を使用して、要素がキューにあるかどうかを確認します。最後に、残りの値を出力するために、toArray() を使用してキューを配列に変換します。
import java.util.*;
public class JavaMinHeap {
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(10);
priorityQueue.add(15);
priorityQueue.add(25);
priorityQueue.add(200);
System.out.println("The head value using peek(): " + priorityQueue.peek());
System.out.println("The queue elements: ");
for (Integer integer : priorityQueue) System.out.println(integer);
priorityQueue.poll();
System.out.println("After removing the head element using poll(): ");
for (Integer integer : priorityQueue) System.out.println(integer);
priorityQueue.remove(25);
System.out.println("After removing 25 with remove(): ");
for (Integer integer : priorityQueue) System.out.println(integer);
boolean b = priorityQueue.contains(15);
System.out.println("Check if priorityQueue contains 15 using contains(): " + b);
Object[] arr = priorityQueue.toArray();
System.out.println("Values in array: ");
for (Object o : arr) System.out.println("Value: " + o.toString());
}
}
出力：
The head value using peek(): 10
The queue elements:
10
15
25
200
After removing the head element using poll():
15
200
25
After removing 25 with remove():
15
200
Check if priorityQueue contains 15 using contains(): true
Values in array:
Value: 15
Value: 200
Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.
LinkedIn