バイナリ ツリー
Java には、さまざまなタイプのデータ構造があります。ヒープは、バイナリ ツリーと呼ばれるツリー構造に基づいています。バイナリ ツリーはノードで構成され、各ノードは最大 2 つの子ノードを持つことができます。

最大ヒープ
Max heap (または maxheap) は完全なバイナリ ツリーです。ここで重要なことは、親ノードは左および右の子ノードの値以上の値を持たなければならないということです。これが守られていない場合、最大ヒープが得られません。一方、最小ヒープはその逆で、ルートが最小値となり、連続するノードの値が増加します。各子ノードは、その親ノード以上の値を持ちます。これは完全な二分木でもあります。最大ヒープの例は次のとおりです。
PriorityQueue クラス
Java のヒープは、 PriorityQueueクラスを使用して実装できます。PriorityQueue は、コレクション内で最も重要な項目または最も重要でない項目を検索するために使用されます。PriorityQueueクラスはjava.util.packageにあります。PriorityQueue は、キュー内で特定の順序で配置されるように、比較可能なオブジェクトで構成されている必要があります。PriorityQueue にはコンパレータを含めることができるため、オブジェクト間の比較が行われ、この比較に従ってキューが形成されます。例は次のとおりです。
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main
{
public static void main(String[] args) {
// Create PriorityQueue with comparator for ascending order of array length
PriorityQueue intQueue = new PriorityQueue((a,b) -> a - b);
Integer [] array1 = {1, 2, 4, 6, 8, 9};
Integer [] array2 = {3, 6, 9};
Integer [] array3 = {2, 4, 8, 16, 32, 64, 128};
Integer [] array4 = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55};
Integer [] array5 = {4};
//Add the array lengths to intQueue
intQueue.add(array1.length);
intQueue.add(array2.length);
intQueue.add(array3.length);
intQueue.add(array4.length);
intQueue.add(array5.length);
//Write out contents of intQueue as stored
while (intQueue.size() != 0) {
System.out.println(intQueue.remove());
}
}
}
出力を与える:
1 3 6 7 11
この例では、 intQueue のデフォルト サイズは11 であるため、指定されておらず (通常はコンパレータの前の最初の引数)、コンパレータは次のように指定されています。
(a,b) -> a - b
これにより、 intQueue 内の項目間の比較が行われ、配列の長さの昇順に並べ替えられます。
最大ヒープを作成するための PriorityQueue の実装
PriorityQueueクラスのデフォルトは、コンパレータなしの最小ヒープです。最小ヒープは最大ヒープの逆であるため、ルートが最小値となり、連続する子ノードはルートおよび後続の親ノード以上になります。このため、最大ヒープの場合は、Java の Collections フレームワークのreverseOrder() をコンパレータとして使用する必要があります。これにより、最小ヒープではなく最大ヒープが得られます。このクラスには、add()、contains()、remove()、poll()、peek()などの便利なメソッドがあります。方法 | 説明 | 時間計算量 |
---|---|---|
追加(J) | 要素 J をツリーの最後に追加します | O(LogN) |
削除(J) | 値 J をツリーから削除します | の上) |
ポーリング() | ツリーの最大要素を削除します | O(LogN) |
ピーク() | ツリーの最上位にあるルート要素を返します | ○(1) |
含む(J) | J がキュー内にある場合は true、そうでない場合は false を返します。 | の上) |

mport java.util.Collections;
import java.util.PriorityQueue;
public class MaxHeap {
public static void writeQueue(PriorityQueue<Integer> priorityQueue)
{
// Write out elements in queue, priorityQueue, and remove them using poll()
while(priorityQueue.size() != 0)
{
System.out.println(priorityQueue.poll());
}
}
public static void writeMaxHeap(PriorityQueue<Integer> priorityQueue)
{
// Write out elements in queue as a max heap - root, left child, right child, etc
for (Integer element : priorityQueue) {
System.out.println(element);
}
}
public static void main(String args[])
{
// Array of numbers to create a max heap array from
int[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};
// theQueue is created
PriorityQueue<Integer> theQueue =
new PriorityQueue<Integer>(Collections.reverseOrder());
// Elements are added to theQueue
for (int i = 0 ; i <theArray.length; ++i)
{
theQueue.add(theArray[i]);
}
// The head or root element (priority element) is printed out
System.out.println("The root value is : " + theQueue.peek());
// Find size of theQueue. Use method size()
Integer s = theQueue.size();
System.out.println("Size of theQueue? " + s);
// All elements of theQueue are printed in terms of parent,
// left child, right child
System.out.println("theQueue written using for loop:");
writeMaxHeap(theQueue);
// Does theQueue contain 10? Use method contains()
boolean b = theQueue.contains(10);
System.out.println("Does theQueue contain 10? " + b);
// Erasing value 10 from array using remove()
theQueue.remove(10);
// All elements of theQueue are printed out and removed.
// Each one is the maximum value left in the queue.
// At the end theQueue will be empty
System.out.println("theQueue written out using poll():");
writeQueue(theQueue);
// Find size of theQueue. Use method size()
s = theQueue.size();
System.out.println("Size of theQueue? " + s);
}
}
出力:
99 キューのサイズ? 9 for ループを使用して書き込まれたキュー 99 51 19 13 10 5 6 3 9 theQueue には 10 が含まれていますか? true poll() を使用して書き出された Queue 99 51 19 13 9 6 5 3 キューのサイズ? 0
マックスヒーピファイ
Max Heapify アルゴリズムは、バイナリ ツリーが最大ヒープであることを保証するために使用されます。ノード n とその子ノードの左右も最大ヒープである場合、最大ヒープを持っています。これがツリー全体に当てはまらない場合は、最大ヒープがありません。Max Heapify アルゴリズムは、maxheap の原則に従うようにツリーをソートするために使用されます。Max Heapify は 1 つのノードでのみ動作します。配列が最大ヒープ配列であることが要件の場合、ルートの前にすべてのサブツリーを一度に 1 つずつ maxheap に変換する必要があります。アルゴリズムは各ノードで使用する必要があります。これは N/2 ノードで実行されます (リーフは最大ヒープ要件に従います)。ヒープの時間計算量は O(NlogN) で、高さ X にある 1 つのノードの場合、時間計算量は O(X) です。次のコードは、ツリー (配列) を maxheapify する方法を示しています。
public class MaxHeapify
{
public static Integer[] maxHeapify(Integer[ ] array, Integer i)
{
// Create left-child and right-child for the node in question
Integer leftChild = 2 * i + 1;
Integer rightChild = 2 * i + 2;
// Assign maxVal to parent node, i
Integer maxVal = i;
// Set maxVal to greater of the two: node or left-child
if( leftChild < array.length && array[leftChild] > array[maxVal] )
maxVal = leftChild;
// Set maxVal to greater of the two: maxVal or right-child
if( rightChild < array.length && array[rightChild] > array[maxVal] )
maxVal = rightChild;
// Check if maxVal is not equal to parent node, then set parent node to
// maxVal, swap values and then do a maxheapify on maxVal
// which is now the previous parent node
if( maxVal != i )
{
Integer value = array[i];
array[i] = array[maxVal];
array[maxVal] = value;
array = maxHeapify(array, maxVal);
}
return array;
}
public static Integer[] maxHeapCreate(Integer array[])
{
// Call maxHeapify to arrange array in a max heap
Integer [] theNewArr = array;
for( Integer i = array.length/2; i >= 0; i-- )
theNewArr = maxHeapify(array, i);
return theNewArr;
}
public static void main(String[] args)
{
// Create array to be maxheapified, theArray,
// and array, newArray, to write results into, by calling maxheapCreate
// newArray will now be a maxheap
Integer[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};
Integer[ ] newArray = maxHeapCreate(theArray);
// Print out contents of newArray
System.out.println("newArray:");
for(int i = 0; i < newArray.length; ++i)
{
System.out.println(newArray[i]);
}
// Print out labelled contents of newArray
System.out.println(" root : " + newArray[0]);
for (int i = 0; i <= newArray.length/2 - 1; i++) {
System.out.print(" parent node : " + newArray[i] + " left child : " +
newArray[(2*i)+1] + " right child :" + newArray[(2*i)+2]);
System.out.println();
}
}
}
出力を与える:
新しい配列:99 51 19 10 3 13 65 9 ルート:99 親ノード:99 左の子:51 右の子:19 親ノード:51 左の子:10 右の子:3 親ノード:19 左の子:13 右の子:6 親ノード:10 左の子:5 右子供:9人99999999 親ノード:99 左の子:51 右の子:19 親ノード:51 左の子:10 右の子:3 親ノード:19 左の子:13 右の子:6 親ノード:10 左の子:5 右の子:999 親ノード:99 左の子:51 右の子:19 親ノード:51 左の子:10 右の子:3 親ノード:19 左の子:13 右の子:6 親ノード:10 左の子:5 右の子:96 親ノード : 10 左の子ノード : 5 右の子ノード : 96 親ノード : 10 左の子ノード : 5 右の子ノード : 9
このコードでは、Arrayが作成され、数値が入力されます。2 番目の配列newArrayが作成され、今回はメソッドmaxheapCreateの結果である最大ヒープ配列が含まれます。メソッドmaxHeapCreateがmainから呼び出され、ここで新しい配列theNewArr が作成され、 maxHeapify の結果が格納されます。これは、入力配列のサイズの半分をループすることによって行われます。ループのパスごとに、メソッドmaxHeapifyが配列の中央の要素から開始して最初の要素で終了するまで呼び出されます。maxHeapifyの呼び出しごとに、親ノード i の左の子と右の子が見つかり、3 つのうちのどれが大きいかを調べるチェックが行われ、それをmaxValとして定義します。maxValが親ノードと等しくない場合は、親ノードとmaxVal が交換されるようにスワップが実行され、今度はmaxValに対してmaxHeapify が再度呼び出され、前と同じ手順が実行されます。最終的には最大ヒープが作成され、それ以上反復を実行する必要はなくなります。更新された配列 array はnewArrayとしてmainに返され、連続する各要素がコンソールに出力されます。新しい配列は最大ヒープになりました。PriorityQueueを使用する前の例と同様に、番号が書き出されることに注意してください: ルート、親としてのルートの右の子、親としてのルートの左の子、最初の右の子、親としての右の子、最初の左の子left-child を親、最初の left-child の right-child を親、最初の right-child の left-child を親とするなど。連続した要素間で比較が行われるため、PriorityQueue を使用する場合の順序とは若干異なります。一方、maxheapify の例では、ノードは配列内の次の 2 つの連続する要素と比較され、最大値と交換されます。つまり、2 つの異なるアルゴリズムが使用されます。どちらも最大ヒープを作成します。
GO TO FULL VERSION