あ 最大ヒープ は、各内部ノードの値がそのノードの子の値以上である完全なバイナリ ツリーです。ヒープの要素を配列にマッピングするのは簡単です。ノードがインデックス k に格納されている場合、その左の子はインデックス 2k + 1 に格納され、右の子はインデックス 2k + 2 に格納されます。
図： 最大ヒープ
Android携帯電話のiPhone絵文字
最大ヒープはどのように表されますか?
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>(サイズ />>' >return> true>;> >}> >return> false>;> >}> >// Method 5> >// Swapping nodes> >private> void> swap(>int> fpos,>int> spos)> >{> >int> tmp;> >tmp = Heap[fpos];> >Heap[fpos] = Heap[spos];> >Heap[spos] = tmp;> >}> >// Method 6> >// Recursive function to max heapify given subtree> >private> void> maxHeapify(>int> pos)> >{> >if> (isLeaf(pos))> >return>;> >if> (Heap[pos] || Heap[pos] if (Heap[leftChild(pos)]>Heap[rightChild(pos)]) { swap(pos, leftChild(pos)); maxHeapify(leftChild(pos)); } else { swap(pos, rightChild(pos)); maxHeapify(rightChild(pos)); } } } // メソッド 7 // 新しい要素を最大ヒープに挿入します public void insert(int element) { Heap[size] = element; // 上にトラバースして、違反したプロパティを修正します。 int current = size; while (ヒープ[現在]> ヒープ[親(現在)]) { swap(現在, 親(現在)); 現在 = 親(現在); サイズ++; } // メソッド 8 // ヒープを表示するには public void print() { for (int i = 0; i 2; i++) { System.out.print('Parent Node : ' + Heap[i]); if (leftChild(i) // 子が配列の範囲外にある場合 // System.out.print(' Left Child Node: ' + Heap[leftChild(i)]); if (rightChild(i) ) // 右側の子のインデックスは、 // 配列のインデックスの外であってはなりません System.out.print(' Right Child Node: ' + Heap[rightChild(i)]); ; // 新しい行 } } // メソッド 9 // 最大ヒープから要素を削除します public int extractMax() { int popped = Heap[0] = Heap[--size]; ; return Popped; } // メソッド 10 // メイン ドライバー メソッド public static void main(String[] arg) { // 読みやすくするためにメッセージを表示します System.out.println('最大ヒープは '); = new MaxHeap(15); // カスタム入力 maxHeap.insert(17); maxHeap.insert(19); maxHeap.insert(22); // 上記の定義に従って maxHeap() を呼び出し、最大値を表示します。ヒープ内の値 System.out.println('最大値は ' + maxHeap.extractMax()); } }>> |
>
>出力
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() メソッドを使用します。
例
ジャワ
jpa と休止状態の比較
// 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>