Max-Heap の概要 – データ構造とアルゴリズムのチュートリアル
あ 最大ヒープ のタイプとして定義されます ヒープ データ構造は、データの並べ替え、検索、整理などのさまざまな目的でコンピューター サイエンスで一般的に使用されるバイナリ ツリーの一種です。
Max-Heap データ構造の概要
Max-Heap の目的と使用例:
- 優先キュー: ヒープ データ構造の主な用途の 1 つは、優先キューを実装することです。
- ヒープソート: ヒープ データ構造は、並べ替えアルゴリズムでも使用されます。
- メモリ管理： ヒープ データ構造はメモリ管理にも使用されます。プログラムがメモリを動的に割り当てる必要がある場合、ヒープ データ構造を使用して利用可能なメモリを追跡します。
- ダイクストラの最短経路アルゴリズム は、ヒープ データ構造を使用して、ソース頂点からの最短パスを持つ頂点を追跡します。
さまざまな言語での Max-Heap データ構造:
1. C++ の最大ヒープ
最大ヒープは、次を使用して実装できます。 優先キュー からのコンテナ 標準テンプレート ライブラリ (STL) 。の 優先キュー コンテナは、各要素に優先順位が関連付けられたキューのようなデータ構造に要素を格納する方法を提供するコンテナ アダプタの一種です。
Synt ax: priority_queuemaxH;2. Java の最大ヒープ
Java では、最大ヒープは次を使用して実装できます。 優先キュー からのクラス java.util パッケージ 。 PriorityQueue クラスは、各要素に関連付けられた優先順位を持つキューのようなデータ構造に要素を格納する方法を提供する優先キューです。
Syntax : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());3. Python の最大ヒープ
Python では、最大ヒープは次を使用して実装できます。 ヒープク ヒープを実装するための機能を提供するモジュール。具体的には、heapq モジュールは、ヒープ データ構造を作成および操作する方法を提供します。
Synt ax: heap = [] heapify(heap)4. C# の最大ヒープ
C# では、最大ヒープは、次の PriorityQueue クラスを使用して実装できます。 System.Collections.Generic 名前空間 。 PriorityQueue クラスは、各要素に関連付けられた優先順位を持つキューのようなデータ構造に要素を格納する方法を提供する優先キューです。
Syntax: var maxHeap = new PriorityQueue((a, b) =>b - a);>5. JavaScript の最大ヒープ
最大ヒープは、すべてのノードがその子以上の値を持つバイナリ ツリーです。 JavaScript では、配列を使用して最大ヒープを実装できます。最初の要素はルート ノードを表し、インデックスにあるノードの子を表します。 私 インデックスにあります 2i+1 そして 2i+2。
Syntax: const miaxHeap = new MaxHeap();最大ヒープと最小ヒープの違い
最小ヒープ 最大ヒープ 1. Min-Heap では、ルート ノードに存在するキーは、そのすべての子に存在するキー以下である必要があります。 Max-Heap では、ルート ノードに存在するキーは、そのすべての子に存在するキー以上である必要があります。 2. Min-Heap では、ルートに存在する最小のキー要素。 Max-Heap では、ルートに存在する最大のキー要素。 3. 最小ヒープでは昇順の優先順位が使用されます。 Max-Heap では降順の優先順位が使用されます。 4. Min-Heap の構築では、最小の要素が優先されます。 Max-Heap の構築では、最大の要素が優先されます。 5. Min-Heap では、最小の要素が最初にヒープからポップされます。 Max-Heap では、最大の要素が最初にヒープからポップされます。 Max-Heap データ構造の内部実装:
あ 最小ヒープは通常、配列として表されます 。
- ルート要素は次の場所になります。 到着[0] 。
- 任意の i 番目のノードの場合 ありました。
- 左の子はインデックスに格納されます 2i+1
- 右の子はインデックスに格納されます 2i+2
- 親はインデックスフロアに格納されます ((i-1)/2)
Max-Heap の内部実装には、次の 3 つの主要な手順が必要です。
- 挿入 : 新しい要素をヒープに挿入するには、その要素が配列の最後に追加され、ヒープ プロパティを満たすまでバブルアップされます。
- 削除 : 最大要素 (ヒープのルート) を削除するには、配列内の最後の要素がルートと交換され、新しいルートがヒープ プロパティを満たすまでバブルダウンされます。
- ヒーピファイ : ヒープ化操作を使用して、ソートされていない配列から最大ヒープを作成できます。
最大ヒープ データ構造の操作とその実装:
ヒープ データ構造データ構造に対して実行できる一般的な操作をいくつか示します。
1. 最大ヒープ データ構造への挿入 :
要素は、削除に関して上で説明したのと同様のアプローチに従ってヒープに挿入できます。アイデアは次のとおりです。
- まず、新しい要素を格納できるようにヒープ サイズを 1 増やします。
- 新しい要素をヒープの最後に挿入します。
- この新しく挿入された要素は、その親のヒープのプロパティを歪める可能性があります。したがって、ヒープのプロパティを維持するには、ボトムアップのアプローチに従って、この新しく挿入された要素をヒープ化します。
図：
ヒープが次のような Max-Heap であると仮定します。
Max ヒープへの挿入
Max-Heap での挿入操作の実装:
C++
// C++ program to insert new element to Heap>#include>using>namespace>std;>#define MAX 1000 // Max size of Heap>// Function to heapify ith node in a Heap>// of size n following a Bottom-up approach>void>heapify(>int>arr[],>int>n,>int>i)>{>>// Find parent>>int>parent = (i - 1) / 2;>>if>(arr[parent]>0) {>>>// For Max-Heap>>// If current node is greater than its parent>>// Swap both of them and call heapify again>>// for the parent>>if>(arr[i]>arr[親]) {>>>swap(arr[i], arr[parent]);>>// Recursively heapify the parent node>>heapify(arr, n, parent);>>}>>}>}>// Function to insert a new node to the Heap>void>insertNode(>int>arr[],>int>& n,>int>Key)>{>>// Increase the size of Heap by 1>>n = n + 1;>>// Insert the element at end of Heap>>arr[n - 1] = Key;>>// Heapify the new node following a>>// Bottom-up approach>>heapify(arr, n, n - 1);>}>// A utility function to print array of size n>void>printArray(>int>arr[],>int>n)>{>>for>(>int>i = 0; i cout < < arr[i] < < ' '; cout < < ' '; } // Driver Code int main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[MAX] = { 10, 5, 3, 2, 4 }; int n = 5; int key = 15; insertNode(arr, n, key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 return 0; }>
ジャワ
// Java program for implementing insertion in Heaps>public>class>insertionHeap {>>// Function to heapify ith node in a Heap>>// of size n following a Bottom-up approach>>static>void>heapify(>int>[] arr,>int>n,>int>i)>>{>>// Find parent>>int>parent = (i ->1>) />2>;>>>if>(arr[parent]>>>0>) {>>// For Max-Heap>>// If current node is greater than its parent>>// Swap both of them and call heapify again>>// for the parent>>if>(arr[i]>arr[親]) {>>>>// swap arr[i] and arr[parent]>>int>temp = arr[i];>>arr[i] = arr[parent];>>arr[parent] = temp;>>>// Recursively heapify the parent node>>heapify(arr, n, parent);>>}>>}>>}>>// Function to insert a new node to the heap.>>static>int>insertNode(>int>[] arr,>int>n,>int>Key)>>{>>// Increase the size of Heap by 1>>n = n +>1>;>>>// Insert the element at end of Heap>>arr[n ->1>] = Key;>>>// Heapify the new node following a>>// Bottom-up approach>>heapify(arr, n, n ->1>);>>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size n */>>static>void>printArray(>int>[] arr,>int>n)>>{>>for>(>int>i =>0>; i System.out.println(arr[i] + ' '); System.out.println(); } // Driver Code public static void main(String args[]) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 // maximum size of the array int MAX = 1000; int[] arr = new int[MAX]; // initializing some values arr[0] = 10; arr[1] = 5; arr[2] = 3; arr[3] = 2; arr[4] = 4; // Current size of the array int n = 5; // the element to be inserted int Key = 15; // The function inserts the new element to the heap and // returns the new size of the array n = insertNode(arr, n, Key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 } } // The code is contributed by Gautam goel>
C#
// C# program for implementing insertion in Heaps>using>System;>public>class>insertionHeap {>>// Function to heapify ith node in a Heap of size n following a Bottom-up approach>>static>void>heapify(>int>[] arr,>int>n,>int>i) {>>// Find parent>>int>parent = (i - 1) / 2;>>if>(arr[parent]>0) {>>>// For Max-Heap>>// If current node is greater than its parent>>// Swap both of them and call heapify again>>// for the parent>>if>(arr[i]>arr[親]) {>>>// swap arr[i] and arr[parent]>>int>temp = arr[i];>>arr[i] = arr[parent];>>arr[parent] = temp;>>// Recursively heapify the parent node>>heapify(arr, n, parent);>>}>>}>>}>>// Function to insert a new node to the heap.>>static>int>insertNode(>int>[] arr,>int>n,>int>Key) {>>// Increase the size of Heap by 1>>n = n + 1;>>// Insert the element at end of Heap>>arr[n - 1] = Key;>>// Heapify the new node following a>>// Bottom-up approach>>heapify(arr, n, n - 1);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size n */>>static>void>printArray(>int>[] arr,>int>n) {>>for>(>int>i = 0; i Console.WriteLine(arr[i] + ' '); Console.WriteLine(''); } public static void Main(string[] args) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 // maximum size of the array int MAX = 1000; int[] arr = new int[MAX]; // initializing some values arr[0] = 10; arr[1] = 5; arr[2] = 3; arr[3] = 2; arr[4] = 4; // Current size of the array int n = 5; // the element to be inserted int Key = 15; // The function inserts the new element to the heap and // returns the new size of the array n = insertNode(arr, n, Key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 } } // This code is contributed by ajaymakvana.>
JavaScript
// Javascript program for implement insertion in Heaps>// To heapify a subtree rooted with node i which is>// an index in arr[].Nn is size of heap>let MAX = 1000;>// Function to heapify ith node in a Heap of size n following a Bottom-up approach>function>heapify(arr, n, i)>{>>// Find parent>>let parent = Math.floor((i-1)/2);>>if>(arr[parent]>= 0) {>>>// For Max-Heap>>// If current node is greater than its parent>>// Swap both of them and call heapify again>>// for the parent>>if>(arr[i]>arr[親]) {>>>let temp = arr[i];>>arr[i] = arr[parent];>>arr[parent] = temp;>>// Recursively heapify the parent node>>heapify(arr, n, parent);>>}>>}>}>// Function to insert a new node to the Heap>function>insertNode(arr, n, Key)>{>>// Increase the size of Heap by 1>>n = n + 1;>>// Insert the element at end of Heap>>arr[n - 1] = Key;>>// Heapify the new node following a>>// Bottom-up approach>>heapify(arr, n, n - 1);>>>return>n;>}>/* A utility function to print array of size N */>function>printArray(arr, n)>{>>for>(let i = 0; i console.log(arr[i] + ' '); console.log(''); } let arr = [ 10, 5, 3, 2, 4 ]; let n = arr.length; let key = 15; n = insertNode(arr, n, key); printArray(arr, n); // This code is contributed by ajaymakvana>
Python3
# program to insert new element to Heap># Function to heapify ith node in a Heap># of size n following a Bottom-up approach>def>heapify(arr, n, i):>>parent>=>int>(((i>->1>)>/>2>))>># For Max-Heap>># If current node is greater than its parent>># Swap both of them and call heapify again>># for the parent>>if>arr[parent]>>>0>:>>if>arr[i]>arr[親]:>>>arr[i], arr[parent]>=>arr[parent], arr[i]>># Recursively heapify the parent node>>heapify(arr, n, parent)># Function to insert a new node to the Heap>def>insertNode(arr, key):>>global>n>># Increase the size of Heap by 1>>n>+>=>1>># Insert the element at end of Heap>>arr.append(key)>># Heapify the new node following a>># Bottom-up approach>>heapify(arr, n, n>->1>)># A utility function to print array of size n>def>printArr(arr, n):>>for>i>in>range>(n):>>print>(arr[i], end>=>' '>)># Driver Code># Array representation of Max-Heap>'''>>10>>/>>5 3>>/>>2 4>'''>arr>=>[>10>,>5>,>3>,>2>,>4>,>1>,>7>]>n>=>7>key>=>15>insertNode(arr, key)>printArr(arr, n)># Final Heap will be:>'''>>15>>/>5 10>/ />2 4 3>Code is written by Rajat Kumar....>'''>
出力
15 5 10 2 4 3時間計算量: O(log(n)) ( ここで、n はヒープ内の要素の番号です。 )
補助スペース: の上）2. 最大ヒープ データ構造の削除 :
ヒープ内の中間位置にある要素を削除するとコストが高くなる可能性があるため、削除する要素を最後の要素に置き換えて、ヒープの最後の要素を削除するだけで済みます。
- 削除するルートまたは要素を最後の要素に置き換えます。
- ヒープから最後の要素を削除します。
- 最後の要素がルート ノードの位置に配置されるようになりました。そのため、ヒープのプロパティに従わない可能性があります。したがって、ルートの位置に配置された最後のノードを山盛りにします。
図 :
ヒープが次のような Max-Heap であると仮定します。
最大ヒープ データ構造
削除する要素はルート、つまり 10 です。
プロセス :
最後の要素は 4 です。
ステップ1： 最後の要素をルートに置き換えて削除します。
最大ヒープ
ステップ2 : 根元を盛り上げます。
最終ヒープ:
最大ヒープ
Max-Heap での削除操作の実装:
C++
// C++ program for implement deletion in Heaps>#include>using>namespace>std;>// To heapify a subtree rooted with node i which is>// an index of arr[] and n is the size of heap>void>heapify(>int>arr[],>int>n,>int>i)>{>>int>largest = i;>// Initialize largest as root>>int>l = 2 * i + 1;>// left = 2*i + 1>>int>r = 2 * i + 2;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i) {>>swap(arr[i], arr[largest]);>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>}>// Function to delete the root from Heap>void>deleteRoot(>int>arr[],>int>& n)>{>>// Get the last element>>int>lastElement = arr[n - 1];>>// Replace root with last element>>arr[0] = lastElement;>>// Decrease size of heap by 1>>n = n - 1;>>// heapify the root node>>heapify(arr, n, 0);>}>/* A utility function to print array of size n */>void>printArray(>int>arr[],>int>n)>{>>for>(>int>i = 0; i cout < < arr[i] < < ' '; cout < < ' '; } // Driver Code int main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[] = { 10, 5, 3, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); deleteRoot(arr, n); printArray(arr, n); return 0; }>
ジャワ
// Java program for implement deletion in Heaps>public>class>deletionHeap {>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>static>void>heapify(>int>arr[],>int>n,>int>i)>>{>>int>largest = i;>// Initialize largest as root>>int>l =>2>* i +>1>;>// left = 2*i + 1>>int>r =>2>* i +>2>;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i) {>>int>swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>static>int>deleteRoot(>int>arr[],>int>n)>>{>>// Get the last element>>int>lastElement = arr[n ->1>];>>// Replace root with first element>>arr[>0>] = lastElement;>>// Decrease size of heap by 1>>n = n ->1>;>>// heapify the root node>>heapify(arr, n,>0>);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>static>void>printArray(>int>arr[],>int>n)>>{>>for>(>int>i =>0>; i System.out.print(arr[i] + ' '); System.out.println(); } // Driver Code public static void main(String args[]) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[] = { 10, 5, 3, 2, 4 }; int n = arr.length; n = deleteRoot(arr, n); printArray(arr, n); } }>
C#
// C# program for implement deletion in Heaps>using>System;>public>class>deletionHeap>{>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>static>void>heapify(>int>[]arr,>int>n,>int>i)>>{>>int>largest = i;>// Initialize largest as root>>int>l = 2 * i + 1;>// left = 2*i + 1>>int>r = 2 * i + 2;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i)>>{>>int>swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>static>int>deleteRoot(>int>[]arr,>int>n)>>{>>// Get the last element>>int>lastElement = arr[n - 1];>>// Replace root with first element>>arr[0] = lastElement;>>// Decrease size of heap by 1>>n = n - 1;>>// heapify the root node>>heapify(arr, n, 0);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>static>void>printArray(>int>[]arr,>int>n)>>{>>for>(>int>i = 0; i Console.Write(arr[i] + ' '); Console.WriteLine(); } // Driver Code public static void Main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int []arr = { 10, 5, 3, 2, 4 }; int n = arr.Length; n = deleteRoot(arr, n); printArray(arr, n); } } // This code is contributed by Ryuga>
JavaScript
>>// Javascript program for implement deletion in Heaps>>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>function>heapify(arr, n, i)>>{>>let largest = i;>// Initialize largest as root>>let l = 2 * i + 1;>// left = 2*i + 1>>let r = 2 * i + 2;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i)>>{>>let swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>function>deleteRoot(arr, n)>>{>>// Get the last element>>let lastElement = arr[n - 1];>>// Replace root with first element>>arr[0] = lastElement;>>// Decrease size of heap by 1>>n = n - 1;>>// heapify the root node>>heapify(arr, n, 0);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>function>printArray(arr, n)>>{>>for>(let i = 0; i document.write(arr[i] + ' '); document.write(''); } let arr = [ 10, 5, 3, 2, 4 ]; let n = arr.length; n = deleteRoot(arr, n); printArray(arr, n); // This code is contributed by divyeshrabdiya07.>
Python3
# Python 3 program for implement deletion in Heaps># To heapify a subtree rooted with node i which is># an index of arr[] and n is the size of heap>def>heapify(arr, n, i):>>largest>=>i>#Initialize largest as root>>l>=>2>*>i>+>1># left = 2*i + 1>>r>=>2>*>i>+>2># right = 2*i + 2>>#If left child is larger than root>>if>(l and arr[l]>arr[最大]):最大 = l #右の子がこれまでの最大より大きい場合 if (r および arr[r]> arr[最大]):最大 = r #最大がルートではない場合 if (最大 != i) : arr[i],arr[largest]=arr[largest],arr[i] #影響を受けるサブツリーを再帰的にヒープ化 heapify(arr, n, biggest) #ヒープからルートを削除する関数 def deleteRoot(arr): global n # 最後の要素を取得します lastElement = arr[n - 1] # ルートを最後の要素に置き換えます arr[0] = lastElement # ヒープのサイズを 1 だけ減らします n = n - 1 # ルートノードをヒープ化します heapify(arr, n, 0) # サイズ n の配列を出力するユーティリティ関数 def printArray(arr, n): for i in range(n): print(arr[i],end=' ') print() # ドライバー コード if __name__ == '__main__': # Max-Heap の配列表現 # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # このコードは Rajat Kumar によって提供されました。>>
出力
5 4 3 2時間計算量 : O(log n) ここで、n はヒープ内の要素の数です。
補助スペース: の上）3. 最大ヒープ データ構造に対するピーク操作:
最大の要素 (つまり、ヒープのルート) にアクセスするには、ルート ノードの値が返されます。最大ヒープ内のピークの時間計算量は O(1) です。
最大ヒープのピーク要素
Max-Heap での Peek 操作の実装:
C++
#include>#include>int>main() {>>// Create a max heap with some elements using a priority_queue>>std::priority_queue <>int>>maxHeap;>>'< < peakElement < < std::endl;>>return>0;>}>
ジャワ
import>java.util.PriorityQueue;>public>class>GFG {>>public>static>void>main(String[] args) {>>// Create a max heap with some elements using a PriorityQueue>>PriorityQueue maxHeap =>new>PriorityQueue((a, b) ->b - a);>>+ peakElement);>>}>}>
C#
using>System;>using>System.Collections.Generic;>public>class>GFG {>>public>static>void>Main() {>>// Create a min heap with some elements using a PriorityQueue>>var>maxHeap =>new>PriorityQueue <>int>>();>>+ peakElement);>>}>}>// Define a PriorityQueue class that uses a max heap>class>PriorityQueue>where>T : IComparable {>>private>List heap;>>public>PriorityQueue() {>>this>.heap =>new>List();>>}>>public>int>Count {>>get>{>return>this>.heap.Count; }>>}>>public>void>Enqueue(T item) {>>this>.heap.Add(item);>>this>.BubbleUp(>this>.heap.Count - 1);>>}>>public>T Dequeue() {>>T item =>this>.heap[0];>>int>lastIndex =>this>.heap.Count - 1;>>this>.heap[0] =>this>.heap[lastIndex];>>this>.heap.RemoveAt(lastIndex);>>this>.BubbleDown(0);>>return>item;>>}>>public>T Peek() {>>return>this>.heap[0];>>}>>private>void>BubbleUp(>int>index) {>>while>(index>0) {>>>int>parentIndex = (index - 1) / 2;>>if>(>this>.heap[parentIndex].CompareTo(>this>.heap[index])>= 0) {>>>break>;>>}>>Swap(parentIndex, index);>>index = parentIndex;>>}>>}>>private>void>BubbleDown(>int>index) {>>while>(index <>this>.heap.Count) {>>int>leftChildIndex = index * 2 + 1;>>int>rightChildIndex = index * 2 + 2;>>int>largestChildIndex = index;>>if>(leftChildIndex <>this>.heap.Count &&>this>.heap[leftChildIndex].CompareTo(>this>.heap[largestChildIndex])>0) {>>>largestChildIndex = leftChildIndex;>>}>>if>(rightChildIndex <>this>.heap.Count &&>this>.heap[rightChildIndex].CompareTo(>this>.heap[largestChildIndex])>0) {>>>largestChildIndex = rightChildIndex;>>}>>if>(largestChildIndex == index) {>>break>;>>}>>Swap(largestChildIndex, index);>>index = largestChildIndex;>>}>>}>>private>void>Swap(>int>i,>int>j) {>>T temp =>this>.heap[i];>>this>.heap[i] =>this>.heap[j];>>this>.heap[j] = temp;>>}>}>
JavaScript
// Define a MaxHeap class that uses an array>class MaxHeap {>>constructor() {>>this>.heap = [];>>}>>push(item) {>>this>.heap.push(item);>>this>.bubbleUp(>this>.heap.length - 1);>>}>>pop() {>>let item =>this>.heap[0];>>let lastIndex =>this>.heap.length - 1;>>this>.heap[0] =>this>.heap[lastIndex];>>this>.heap.pop();>>this>.bubbleDown(0);>>return>item;>>}>>peak() {>>return>this>.heap[0];>>}>>bubbleUp(index) {>>while>(index>0) {>>>let parentIndex = Math.floor((index - 1) / 2);>>if>(>this>.heap[parentIndex]>=>>+ peakElement);>
Python3
import>heapq># Create a max heap with some elements using a list>max_heap>=>[>1>,>2>,>3>,>4>,>5>,>6>,>7>,>8>,>9>]>heapq.heapify(max_heap)># Get the peak element (i.e., the largest element)>peak_element>=>heapq.nlargest(>1>, max_heap)[>0>]># Print the peak element>print>(>'Peak element:'>, peak_element)>
出力
Peak element: 9時間計算量 :
- を使用して実装された最大ヒープ内では、 配列 またはリストの場合、ピーク要素は常にヒープのルートに位置するため、一定時間 O(1) でアクセスできます。
- を使用して実装された最大ヒープ内で、 二分木 の場合、ピーク要素は常にツリーのルートに位置するため、O(1) 時間でアクセスすることもできます。
補助スペース: の上）
4. Max-heap データ構造に対する Heapify 操作 :
heapify 操作を使用すると、ソートされていない配列から最大ヒープを作成できます。これは、最後の非リーフ ノードから開始して、すべてのノードがヒープ プロパティを満たすまでバブル ダウン操作を繰り返し実行することによって行われます。最大ヒープ内の heapify の時間計算量は O(n) です。
Max-Heap での Heapify 操作
5. 最大ヒープ データ構造の検索操作 :
最大ヒープ内の要素を検索するには、ヒープを表す配列に対して線形検索を実行できます。ただし、線形探索の時間計算量は O(n) であり、効率的ではありません。したがって、検索は最大ヒープ内で一般的に使用される操作ではありません。
以下は、次を使用して最大ヒープ内の要素を検索する方法を示すコード例です。 std::find() :
C++
#include>#include // for std::priority_queue>using>namespace>std;>int>main() {>>std::priority_queue <>int>>最大ヒープ;>>>// example max heap>>>max_heap.push(10);>>max_heap.push(9);>>max_heap.push(8);>>max_heap.push(6);>>max_heap.push(4);>>int>element = 6;>// element to search for>>bool>found =>false>;>>// Copy the max heap to a temporary queue and search for the element>>std::priority_queue <>int>>temp = max_heap;>>>while>(!temp.empty()) {>>if>(temp.top() == element) {>>found =>true>;>>break>;>>}>>temp.pop();>>}>>if>(found) {>>std::cout < <>'Element found in the max heap.'>< < std::endl;>>}>else>{>>std::cout < <>'Element not found in the max heap.'>< < std::endl;>>}>>return>0;>}>
ジャワ
import>java.util.PriorityQueue;>public>class>GFG {>>public>static>void>main(String[] args) {>>PriorityQueue maxHeap =>new>PriorityQueue((a, b) ->b - a);>>);>>}>else>{>>System.out.println(>'Element not found in the max heap.'>);>>}>>}>}>
C#
using>System;>using>System.Collections.Generic;>class>Program {>>static>void>Main(>string>[] args) {>>// Create a max heap with some elements using a PriorityQueue>>PriorityQueue <>int>>maxHeap =>>maxHeap.Enqueue(10);>>maxHeap.Enqueue(9);>>maxHeap.Enqueue(8);>>maxHeap.Enqueue(6);>>maxHeap.Enqueue(4);>>int>element = 6;>// element to search for>>bool>found =>false>;>>// Copy the max heap to a temporary queue and search for the element>>PriorityQueue <>int>>温度 =>>while>(temp.Count>0) {>>>if>(temp.Peek() == element) {>>found =>true>;>>break>;>>}>>temp.Dequeue();>>}>>if>(found) {>>Console.WriteLine(>'Element found in the max heap.'>);>>}>else>{>>Console.WriteLine(>'Element not found in the max heap.'>);>>}>>}>}>// PriorityQueue class>class>PriorityQueue>where>T : IComparable {>>private>List heap =>new>List();>>public>void>Enqueue(T item) {>>heap.Add(item);>>int>child = heap.Count - 1;>>while>(child>0) {>>>int>parent = (child - 1) / 2;>>if>(heap[child].CompareTo(heap[parent])>0) {>>>T tmp = heap[child];>>heap[child] = heap[parent];>>heap[parent] = tmp;>>child = parent;>>}>else>{>>break>;>>}>>}>>}>>public>T Dequeue() {>>int>last = heap.Count - 1;>>T frontItem = heap[0];>>heap[0] = heap[last];>>heap.RemoveAt(last);>>last--;>>int>parent = 0;>>while>(>true>) {>>int>leftChild = parent * 2 + 1;>>if>(leftChild>最後) {>>>break>;>>}>>int>rightChild = leftChild + 1;>>if>(rightChild <= last && heap[leftChild].CompareTo(heap[rightChild]) < 0) {>>leftChild = rightChild;>>}>>if>(heap[parent].CompareTo(heap[leftChild]) <0) {>>T tmp = heap[parent];>>heap[parent] = heap[leftChild];>>heap[leftChild] = tmp;>>parent = leftChild;>>}>else>{>>break>;>>}>>}>>return>frontItem;>>}>>public>T Peek() {>>return>heap[0];>>}>>public>int>Count {>>get>{>>return>heap.Count;>>}>>}>}>
JavaScript
const maxHeap =>new>PriorityQueue((a, b) =>b - a);>>);>}>else>{>console.log(>'Element not found in the max heap.'>);>}>
Python3
import>heapq>max_heap>=>[>10>,>8>,>7>,>6>,>5>,>3>,>2>,>1>]># example max heap>heapq._heapify_max(max_heap)>element>=>6># element to search for>found>=>False># Copy the max heap to a temporary list and search for the element>temp>=>list>(max_heap)>while>temp:>>if>heapq._heappop_max(temp)>=>=>element:>>found>=>True>>break>if>found:>>print>(>'Element found in the max heap.'>)>else>:>>print>(>'Element not found in the max heap.'>)>
出力
Element found in the max heap.時間計算量 : O(n)、n はヒープのサイズです。
補助スペース ： の上）、Max-Heap データ構造のアプリケーション:
- ヒープソートアルゴリズム: ヒープ データ構造は、ヒープソート アルゴリズムの基礎です。ヒープソート アルゴリズムは、最悪の場合の時間計算量が O(n log n) である効率的なソート アルゴリズムです。ヒープソート アルゴリズムは、データベースのインデックス付けや数値分析などのさまざまなアプリケーションで使用されます。
- メモリ管理： ヒープ データ構造は、メモリ管理システムでメモリを動的に割り当てたり割り当て解除したりするために使用されます。ヒープはメモリ ブロックを格納するために使用され、ヒープ データ構造はメモリ ブロックを効率的に管理し、必要に応じてプログラムに割り当てるために使用されます。
- グラフアルゴリズム: ヒープ データ構造は、ダイクストラのアルゴリズム、プリムのアルゴリズム、クラスカルのアルゴリズムなど、さまざまなグラフ アルゴリズムで使用されます。これらのアルゴリズムには効率的な優先キューの実装が必要ですが、これはヒープ データ構造を使用して実現できます。
- ジョブのスケジュール設定: ヒープ データ構造はジョブ スケジューリング アルゴリズムで使用され、優先順位または期限に基づいてタスクがスケジュールされます。ヒープ データ構造により、最も優先度の高いタスクに効率的にアクセスできるため、ジョブ スケジューリング アプリケーションにとって便利なデータ構造になります。
最大ヒープ データ構造の利点:
- 最大値を効率的に維持します。 最大ヒープを使用すると、ヒープ内の最大要素に一定時間アクセスできるため、最大要素を迅速に見つける必要があるアプリケーションで役立ちます。
- 効率的な挿入および削除操作: 最大ヒープでの挿入操作と削除操作の時間計算量は O(log n) であるため、要素の大規模なコレクションでは効率的になります。
- 優先キュー: 最大ヒープを使用して優先キューを実装できます。これは、ジョブのスケジューリング、タスクの優先順位付け、イベント駆動型シミュレーションなどの多くのアプリケーションで役立ちます。
- 並べ替え: 最大ヒープを使用してヒープソートを実装できます。ヒープソートは、最悪の場合の時間計算量が O(n log n) である効率的な並べ替えアルゴリズムです。
- スペース効率: 最大ヒープは配列として実装できるため、二分探索ツリーやリンク リストなどの他のデータ構造と比較して必要なメモリが少なくなります。
Max ヒープ データ構造は、特に最大の要素に迅速にアクセスする必要がある場合、または要素の並べ替えや優先順位付けが必要な場合に、要素のコレクションを維持および操作するための便利で効率的なツールです。
