Java の最大ヒープ

バイナリ ツリー

Java には、さまざまなタイプのデータ構造があります。ヒープは、バイナリ ツリーと呼ばれるツリー構造に基づいています。バイナリ ツリーはノードで構成され、各ノードは最大 2 つの子ノードを持つことができます。バイナリ ツリーは、0 ～ 2 個のノードを持つことができる親ノードで構成されます。左側の子ノードや右側の子ノードを持つことも、ノードをまったく持たないこともできます。完全なバイナリ ツリーでは、満杯になる可能性がある最後のレベルを除いて、すべてのノードが満杯になりますが、満杯である必要はありません。最後のレベルである n 番目のレベルには 1 ～ 2n のノードを含めることができます。最初のレベルは n = 0 にあり、ルートになります。

最大ヒープ

Max heap (または maxheap) は完全なバイナリ ツリーです。ここで重要なことは、親ノードは左および右の子ノードの値以上の値を持たなければならないということです。これが守られていない場合、最大ヒープが得られません。一方、最小ヒープはその逆で、ルートが最小値となり、連続するノードの値が増加します。各子ノードは、その親ノード以上の値を持ちます。これは完全な二分木でもあります。最大ヒープの例は次のとおりです。最大ヒープは配列から構築できます。この配列はツリーの観点から考えられます。ヒープの場合、ルート (ツリーの最上位の親ノード) が位置 (インデックス) n に格納されている場合、それは配列theArrayに対してtheArray[n]として定義されます。。したがって、左側と右側の子ノードはそれぞれtheArray[2n+1]とtheArray[2n+2]にあります。最大ヒープの場合、ルートはtheArray[0]にあります。レベル n の場合、ルート n = 0: theArr[n] は親ノード theArr[(2*n)+1] は左の子ノード theArr[(2*n)+2] は右の子ノード

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());
        }
    }          
}

出力を与える: この例では、 intQueue のデフォルト サイズは11 であるため、指定されておらず (通常はコンパレータの前の最初の引数)、コンパレータは次のように指定されています。 これにより、 intQueue 内の項目間の比較が行われ、配列の長さの昇順に並べ替えられます。

最大ヒープを作成するための PriorityQueue の実装

PriorityQueueクラスのデフォルトは、コンパレータなしの最小ヒープです。最小ヒープは最大ヒープの逆であるため、ルートが最小値となり、連続する子ノードはルートおよび後続の親ノード以上になります。このため、最大ヒープの場合は、Java の Collections フレームワークのreverseOrder() をコンパレータとして使用する必要があります。これにより、最小ヒープではなく最大ヒープが得られます。このクラスには、add()、contains()、remove()、poll()、peek()などの便利なメソッドがあります。 要素はキューに追加され、任意の順序で追加できます。新しい PriorityQueue キューは、これらの要素を逆の順序で最大ヒープとして保存します。キューが書き出されるときの順序は次のようになります。 ルート ルートを親とする左の子 (Left-child_1) ルートを親とする右の子 (Right-child_1) Left-child_1 を親とする左の子 (Left-child_2) ) Left-child_1 を親とする右子 (Right-child_2) Right-child_1 を親とする左子 (Left-child_3) Right-child_1 を親とする右子 (Right-child_3) Left-child_2 を持つ左子親として (Left-child_4)、Left-child_2 を親として持つ右の子 (Right-child_4) など次のコードは、Java で最大ヒープ (maxheap) を作成する方法の例です。最初に行うことは、最大ヒープが作成される値を配列に入力することです。これはtheArrayと呼ばれます。次に、PriorityQueueであるtheQueueが作成され、theArrayの要素がこれに追加されます。これはメソッドadd()、たとえばtheQueue.add(10)を使用してキューの末尾に 10 を追加します。PriorityQueueクラスの機能の一部を説明するために、メソッドPeak()を使用してヒープの先頭を見つけます。これが最大値であり、この場合は 99 です。次のタスクは、ヒープのサイズを確認することです。size()を使用するこれは 9 であることがわかり、これがコンソールに出力されます。writeMaxHeapメソッドは、ルート、ルートを親とする左子、ルートを親とする右子、最初の左子を親とする左子、最初の左子を持つ右子の順序でキュー内の要素を書き込みます。親、最初の右子を親とする右子、最初の右子を親とする左子など、後続の値は左と右の子を親として上記と同じ順序で使用します。 PriorityQueue メソッドcontains(J)は、特定の要素 J がキュー内にあるかどうかを確認するために使用されます。この例では、J = 10 を探します。この例では、これがキュー内にあるのは事実なので、これは true としてコンソールに書き込まれます。次に、もう 1 つのPriorityQueueメソッド、remove(J)を使用して、 theQueueから J = 10 を削除します。PriorityQueueの機能をさらに詳しく説明するために、メソッドpoll()を使用してwhileループを使用して先頭要素 (最大値) を削除します。そのたびに、新しいキューの先頭要素が削除され、キューのサイズが 1 つずつ減少します。これはwriteQueueメソッドで発生しますメインから呼び出されます。削除されるたびに、要素がコンソールに出力されます。元のキューには最終的に要素が残りません。出力される要素は値の降順の最大ヒープであり、キューの先頭が毎回出力されます。

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);
       }
   }

出力：

マックスヒーピファイ

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();
       }
  }
}

出力を与える: このコードでは、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 つの異なるアルゴリズムが使用されます。どちらも最大ヒープを作成します。

結論

ここでは、最大ヒープと、 PriorityQueueまたは Max Heapify アルゴリズムを使用して最大ヒープを作成する方法について説明しました。PriorityQueueを reverseOrder()とともに使用することは、これを行うための優れた方法であり、推奨される方法です。ただし、これらの例を研究して独自のメソッドを作成することもできます。これは、Java ジュニアの面接で成功するのに役立つ優れたコーディング練習になるからです。