JAVA の最大ヒープ

あ最大ヒープは、各内部ノードの値がそのノードの子の値以上である完全なバイナリツリーです。ヒープの要素を配列にマッピングするのは簡単です。ノードがインデックス k に格納されている場合、その左の子はインデックス 2k + 1 に格納され、右の子はインデックス 2k + 2 に格納されます。

図：最大ヒープ

最大ヒープ

最大ヒープはどのように表されますか?

A-Max ヒープは完全なバイナリツリーです。 A-Max ヒープは通常、配列として表されます。ルート要素は Arr[0] にあります。以下の表は、他のノードのインデックスを示しています。 i番目 ノード、つまり Arr[i]:

Arr[(i-1)/2] 親ノードを返します。
Arr[(2*i)+1] 左側の子ノードを返します。
Arr[(2*i)+2] 右の子ノードを返します。

最大ヒープに対する操作は次のとおりです。

getMax(): Max Heap のルート要素を返します。この操作の時間計算量は次のとおりです。 ○(1) 。
extractMax(): から最大要素を削除します マックスヒープ 。この操作の時間計算量は次のとおりです。 O(ログn) この操作では、 heapify() メソッド 根を取り除いた後。
入れる（）： 新しいキーを挿入するには、 O(ログn) 時間。ツリーの最後に新しいキーを追加します。新しいキーが親キーよりも小さい場合は、何もする必要はありません。それ以外の場合は、上に向かってトラバースして、違反したヒーププロパティを修正する必要があります。

注記： 以下の実装では、実装を簡素化するためにインデックス 1 からインデックスを作成します。

方法:

リストにあるように、目標を達成するには 2 つの方法があります。

作成による基本的な考え方 maxHeapify() 方法
使用する Collections.reverseOrder() ライブラリ関数経由のメソッド

方法 1: 作成による基本的な考え方 maxHeapify() 方法

左右のサブツリーがすでにヒープ化されていると仮定してメソッドを作成します。ルートを修正するだけで済みます。

例

ジャワ

// Java program to implement Max Heap> // Main class> public> class> MaxHeap {> > private> int> [] Heap;> > private> int> size;> > private> int> maxsize;> > // Constructor to initialize an> > // empty max heap with given maximum> > // capacity> > public> MaxHeap(> int> maxsize)> > {> > // This keyword refers to current instance itself> > this> .maxsize = maxsize;> > this> .size => 0> ;> > Heap => new> int> [> this> .maxsize];> > }> > // Method 1> > // Returning position of parent> > private> int> parent(> int> pos) {> return> (pos -> 1> ) /> 2> ; }> > // Method 2> > // Returning left children> > private> int> leftChild(> int> pos) {> return> (> 2> * pos) +> 1> ; }> > // Method 3> > // Returning right children> > private> int> rightChild(> int> pos)> > {> > return> (> 2> * pos) +> 2> ;> > }> > // Method 4> > // Returning true if given node is leaf> > private> boolean> isLeaf(> int> pos)> > {> > if> (pos>(サイズ />>' >

出力

The Max Heap is Parent Node : 84 Left Child Node: 22 Right Child Node: 19 Parent Node : 22 Left Child Node: 17 Right Child Node: 10 Parent Node : 19 Left Child Node: 5 Right Child Node: 6 Parent Node : 17 Left Child Node: 3 Right Child Node: 9 The max val is 84

方法 2: ライブラリ関数を介した Collections.reverseOrder() メソッドの使用

Java でヒープを実装するには、PriorityQueue クラスを使用します。デフォルトでは、最小ヒープはこのクラスによって実装されます。 Max Heap を実装するには、Collections.reverseOrder() メソッドを使用します。

例

ジャワ

// Java program to demonstrate working> // of PriorityQueue as a Max Heap> // Using Collections.reverseOrder() method> // Importing all utility classes> import> java.util.*;> // Main class> class> GFG {> > // Main driver method> > public> static> void> main(String args[])> > {> > // Creating empty priority queue> > PriorityQueue pQueue> > => new> PriorityQueue(> > Collections.reverseOrder());> > // Adding items to our priority queue> > // using add() method> > pQueue.add(> 10> );> > pQueue.add(> 30> );> > pQueue.add(> 20> );> > pQueue.add(> 400> );> > // Printing the most priority element> > System.out.println(> 'Head value using peek function:'> > + pQueue.peek());> > // Printing all elements> > System.out.println(> 'The queue elements:'> );> > Iterator itr = pQueue.iterator();> > while> (itr.hasNext())> > System.out.println(itr.next());> > // Removing the top priority element (or head) and> > // printing the modified pQueue using poll()> > pQueue.poll();> > System.out.println(> 'After removing an element '> > +> 'with poll function:'> );> > Iterator itr2 = pQueue.iterator();> > while> (itr2.hasNext())> > System.out.println(itr2.next());> > // Removing 30 using remove() method> > pQueue.remove(> 30> );> > System.out.println(> 'after removing 30 with'> > +> ' remove function:'> );> > Iterator itr3 = pQueue.iterator();> > while> (itr3.hasNext())> > System.out.println(itr3.next());> > // Check if an element is present using contains()> > boolean> b = pQueue.contains(> 20> );> > System.out.println(> 'Priority queue contains 20 '> > +> 'or not?: '> + b);> > // Getting objects from the queue using toArray()> > // in an array and print the array> > Object[] arr = pQueue.toArray();> > System.out.println(> 'Value in array: '> );> > for> (> int> i => 0> ; i System.out.println('Value: ' + arr[i].toString()); } }>

出力

Head value using peek function:400 The queue elements: 400 30 20 10 After removing an element with poll function: 30 10 20 after removing 30 with remove function: 20 10 Priority queue contains 20 or not?: true Value in array: Value: 20 Value: 10