what is heap data structure java
このチュートリアルでは、Javaヒープのデータ構造と、最小ヒープ、最大ヒープ、ヒープソート、スタックとヒープなどの関連概念を例を挙げて説明します。
ヒープは、Javaの特別なデータ構造です。ヒープはツリーベースのデータ構造であり、完全なバイナリツリーとして分類できます。ヒープのすべてのノードは特定の順序で配置されます。
=> すべてのJavaトレーニングシリーズを見るには、ここにアクセスしてください
学習内容：
Javaのヒープデータ構造
ヒープデータ構造では、ルートノードがその子と比較され、順序に従って配置されます。したがって、aがルートノードで、bがその子である場合、プロパティは キー（a）> =キー（b） 最大ヒープを生成します。
上記のルートノードと子ノードの関係を「ヒーププロパティ」と呼びます。
親子ノードの順序に応じて、ヒープには通常2つのタイプがあります。
＃1）最大ヒープ ：最大ヒープでは、ルートノードキーはヒープ内のすべてのキーの中で最大です。ヒープ内のすべてのサブツリーに同じプロパティが再帰的に当てはまるようにする必要があります。
次の図は、サンプルの最大ヒープを示しています。ルートノードはその子よりも大きいことに注意してください。
＃2）最小ヒープ ：最小ヒープの場合、ルートノードキーは、ヒープ内に存在する他のすべてのキーの中で最小または最小です。 Maxヒープと同様に、このプロパティは、ヒープ内の他のすべてのサブツリーで再帰的に真である必要があります。
例、 最小ヒープツリーの例を以下に示します。ご覧のとおり、ルートキーは、ヒープ内の他のすべてのキーの中で最小です。
ヒープデータ構造は、次の領域で使用できます。
- ヒープは主に優先キューを実装するために使用されます。
- 特にmin-heapは、グラフ内の頂点間の最短パスを決定するために使用できます。
すでに述べたように、ヒープデータ構造は、ルートと子のヒーププロパティを満たす完全なバイナリツリーです。このヒープは、 バイナリヒープ 。
バイナリヒープ
バイナリヒープは、次のプロパティを満たします。
- バイナリヒープは完全なバイナリツリーです。完全な二分木では、最後のレベルを除くすべてのレベルが完全に満たされます。最後のレベルでは、キーは可能な限り左にあります。
- ヒーププロパティを満たします。バイナリヒープは、満たすヒーププロパティに応じて、最大ヒープまたは最小ヒープになります。
バイナリヒープは通常、配列として表されます。完全な二分木であるため、配列として簡単に表すことができます。したがって、バイナリヒープの配列表現では、ルート要素はA (0)になります。ここで、Aはバイナリヒープを表すために使用される配列です。
だから一般的に私はthバイナリヒープ配列表現A (i)のノードでは、以下に示すように他のノードのインデックスを表すことができます。
| A (（i-1）/ 2) | 親ノードを表します |
|---|---|
| アクセスが高速です。 | スタックよりも遅い。 |
| A (（2 * i）+1) | 左の子ノードを表します |
| A (（2 * i）+2) | 右の子ノードを表します |
次のバイナリヒープについて考えてみます。
上記の最小バイナリヒープの配列表現は次のとおりです。
上に示したように、ヒープは次のようにトラバースされます。 レベルの順序 つまり、要素は各レベルで左から右にトラバースされます。あるレベルの要素が使い果たされると、次のレベルに進みます。
次に、Javaでバイナリヒープを実装します。
以下のプログラムは、Javaのバイナリヒープを示しています。
import java.util.*; class BinaryHeap { private static final int d= 2; private int() heap; private int heapSize; //BinaryHeap constructor with default size public BinaryHeap(int capacity){ heapSize = 0; heap = new int( capacity+1); Arrays.fill(heap, -1); } //is heap empty? public boolean isEmpty(){ return heapSize==0; } //is heap full? public boolean isFull(){ return heapSize == heap.length; } //return parent private int parent(int i){ return (i-1)/d; } //return kth child private int kthChild(int i,int k){ return d*i +k; } //insert new element into the heap public void insert(int x){ if(isFull()) throw new NoSuchElementException('Heap is full, No space to insert new element'); heap(heapSize++) = x; heapifyUp(heapSize-1); } //delete an element from the heap at given position public int delete(int x){ if(isEmpty()) throw new NoSuchElementException('Heap is empty, No element to delete'); int key = heap(x); heap(x) = heap(heapSize -1); heapSize--; heapifyDown(x); return key; } //maintain heap property during insertion private void heapifyUp(int i) { int temp = heap(i); while(i>0 && temp > heap(parent(i))){ heap(i) = heap(parent(i)); i = parent(i); } heap(i) = temp; } //maintain heap property during deletion private void heapifyDown(int i){ int child; int temp = heap(i); while(kthChild(i, 1) heap(rightChild)?leftChild:rightChild; } //print the heap public void printHeap() { System.out.print('nHeap = '); for (int i = 0; i 出力：
nHeap = 7 4 6 1 3 2 5
Javaの最小ヒープ
Javaの最小ヒープは、完全なバイナリツリーです。最小ヒープでは、ルートノードはヒープ内の他のすべてのノードよりも小さくなります。一般に、各内部ノードのキー値は、その子ノード以下です。
最小ヒープの配列表現に関する限り、ノードが位置「i」に格納されている場合、その左側の子ノードは位置2i + 1に格納され、右側の子ノードは位置2i +2に格納されます。位置（i-1）/ 2は、その親ノードを返します。
以下に、min-heapでサポートされているさまざまな操作を示します。
＃1）挿入（）： 最初に、新しいキーがツリーの最後に追加されます。キーがその親ノードよりも大きい場合、ヒーププロパティは維持されます。それ以外の場合は、ヒーププロパティを満たすために、キーを上方向にトラバースする必要があります。最小ヒープでの挿入操作にはO（log n）時間がかかります。
＃2）extractMin（）： この操作により、ヒープから最小要素が削除されます。ヒープからルート要素（最小要素）を削除した後も、ヒーププロパティを維持する必要があることに注意してください。この操作全体でO（ログ）が必要です。
＃3）getMin（）： getMin（）は、最小要素でもあるヒープのルートを返します。この操作はO（1）時間で行われます。
以下に、最小ヒープのツリーの例を示します。
上の図は、最小ヒープツリーを示しています。ツリーのルートがツリーの最小要素であることがわかります。ルートは位置0にあるため、左の子は2 * 0 + 1 = 1に配置され、右の子は2 * 0 + 2 = 2に配置されます。
最小ヒープアルゴリズム
以下に示すのは、最小ヒープを構築するためのアルゴリズムです。
procedure build_minheap Array Arr: of size N => array of elements { repeat for (i = N/2 ; i >= 1 ; i--) call procedure min_heapify (A, i); } procedure min_heapify (var A( ) , var i, var N) { var left = 2*i; var right = 2*i+1; var smallest; if(left <= N and A(left) < A( i ) ) smallest = left; else smallest = i; if(right <= N and A(right) < A(smallest) ) smallest = right; if(smallest != i) { swap A( i ) and A( smallest )); call min_heapify (A, smallest,N); } }Javaでの最小ヒープの実装
配列キューまたは優先キューのいずれかを使用して、最小ヒープを実装できます。優先キューは最小ヒープとして実装されるため、優先キューを使用した最小ヒープの実装はデフォルトの実装です。
次のJavaプログラムは、配列を使用して最小ヒープを実装します。ここでは、ヒープの配列表現を使用してから、heapify関数を適用して、ヒープに追加された各要素のheapプロパティを維持します。最後に、ヒープを表示します。
class Min_Heap { private int() HeapArray; private int size; private int maxsize; private static final int FRONT = 1; //constructor to initialize the HeapArray public Min_Heap(int maxsize) { this.maxsize = maxsize; this.size = 0; HeapArray = new int(this.maxsize + 1); HeapArray(0) = Integer.MIN_VALUE; } // returns parent position for the node private int parent(int pos) { return pos / 2; } // returns the position of left child private int leftChild(int pos) { return (2 * pos); } // returns the position of right child private int rightChild(int pos) { return (2 * pos) + 1; } // checks if the node is a leaf node private boolean isLeaf(int pos) { if (pos >= (size / 2) && pos HeapArray(leftChild(pos)) || HeapArray(pos) > HeapArray(rightChild(pos))) { // swap with left child and then heapify the left child if (HeapArray(leftChild(pos)) = maxsize) { return; } HeapArray(++size) = element; int current = size; while (HeapArray(current) = 1; pos--) { minHeapify(pos); } } // remove and return the heap elment public int remove() { int popped = HeapArray(FRONT); HeapArray(FRONT) = HeapArray(size--); minHeapify(FRONT); return popped; } } class Main{ public static void main(String() arg) { //construct a min heap from given data System.out.println('The Min Heap is '); Min_Heap minHeap = new Min_Heap(7); minHeap.insert(12); minHeap.insert(15); minHeap.insert(30); minHeap.insert(40); minHeap.insert(50); minHeap.insert(90); minHeap.insert(45); minHeap.minHeap(); //display the min heap contents minHeap.display(); //display root node of the min heap System.out.println('The Min val(root node):' + minHeap.remove()); } } 出力：
Javaの最大ヒープ
最大ヒープも完全な二分木です。最大ヒープでは、ルートノードは子ノード以上です。一般に、最大ヒープ内の内部ノードの値は、その子ノード以上です。
最大ヒープは配列にマップされますが、ノードが位置「i」に格納されている場合、その左側の子は2i +1に格納され、右側の子は2i +2に格納されます。
一般的な最大ヒープは次のようになります。
上の図では、ルートノードがヒープ内で最大であり、その子ノードの値がルートノードよりも小さいことがわかります。
min-heapと同様に、maxheapも配列として表すことができます。
したがって、Aが最大ヒープを表す配列である場合、A (0)はルートノードです。同様に、A (i)が最大ヒープ内の任意のノードである場合、配列を使用して表すことができる他の隣接ノードは次のとおりです。
- (（i-1）/ 2)は、A (i)の親ノードを表します。
- (（2i +1）)は、A (i)の左の子ノードを表します。
- (2i + 2)は、A (i)の右の子ノードを返します。
最大ヒープで実行できる操作を以下に示します。
＃1）挿入： 挿入操作は、最大ヒープツリーに新しい値を挿入します。ツリーの最後に挿入されます。新しいキー（値）がその親ノードよりも小さい場合、ヒーププロパティは維持されます。それ以外の場合は、ヒーププロパティを維持するためにツリーをヒープ化する必要があります。
無料のプライベートサーバーですごいプレイ
挿入操作の時間計算量はO（log n）です。
＃2）ExtractMax： ExtractMax操作は、最大ヒープから最大要素（ルート）を削除します。この操作では、最大ヒープもヒープ化され、ヒーププロパティが維持されます。この操作の時間計算量はO（log n）です。
＃3）getMax： getMax操作は、時間計算量がO（1）の最大ヒープのルートノードを返します。
以下のJavaプログラムは、最大ヒープを実装します。ここでは、ArrayListを使用して最大ヒープ要素を表します。
import java.util.ArrayList; class Heap { void heapify(ArrayList hT, int i) { int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } void insert(ArrayList hT, int newNum) { int size = hT.size(); if (size == 0) { hT.add(newNum); } else { hT.add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } void deleteNode(ArrayList hT, int num) { int size = hT.size(); int i; for (i = 0; i = 0; j--) { heapify(hT, j); } } void printArray(ArrayList array, int size) { for (Integer i : array) { System.out.print(i + ' '); } System.out.println(); } } class Main{ public static void main(String args()) { ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println('Max-Heap array: '); h.printArray(array, size); h.deleteNode(array, 4); System.out.println('After deleting an element: '); h.printArray(array, size); } } 出力：
Javaの優先キュー最小ヒープ
Javaの優先キューのデータ構造を直接使用して、最小ヒープを表すことができます。デフォルトでは、プライオリティキューは最小ヒープを実装します。
以下のプログラムは、優先度付きキューを使用したJavaの最小ヒープを示しています。
import java.util.*; class Main { public static void main(String args()) { // Create priority queue object PriorityQueue pQueue_heap = new PriorityQueue(); // Add elements to the pQueue_heap using add() pQueue_heap.add(100); pQueue_heap.add(30); pQueue_heap.add(20); pQueue_heap.add(40); // Print the head (root node of min heap) using peek method System.out.println('Head (root node of min heap):' + pQueue_heap.peek()); // Print min heap represented using PriorityQueue System.out.println('
Min heap as a PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // remove head (root of min heap) using poll method pQueue_heap.poll(); System.out.println('
Min heap after removing root node:'); //print the min heap again Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } 出力：
Javaの優先キュー最大ヒープ
Priorityキューを使用してJavaで最大ヒープを表すには、Collections.reverseOrderを使用して最小ヒープを逆にする必要があります。優先度キューは、Javaの最小ヒープを直接表します。
以下のプログラムでは、優先度キューを使用して最大ヒープを実装しました。
import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue //with Collections.reverseOrder to represent max heap PriorityQueue pQueue_heap = new PriorityQueue(Collections.reverseOrder()); // Add items to the pQueue using add() pQueue_heap.add(10); pQueue_heap.add(90); pQueue_heap.add(20); pQueue_heap.add(40); // Printing all elements of max heap System.out.println('The max heap represented as PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // Print the highest priority element (root of max heap) System.out.println('
Head value (root node of max heap):' + pQueue_heap.peek()); // remove head (root node of max heap) with poll method pQueue_heap.poll(); //print the max heap again System.out.println('
Max heap after removing root: '); Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } 出力：
Javaでのヒープソート
ヒープソートは、選択ソートに似た比較ソート手法であり、反復ごとに配列内の最大要素を選択します。ヒープソートは、ヒープデータ構造を利用し、ソートされる配列要素から最小または最大ヒープを作成することによって要素をソートします。
最小ヒープと最大ヒープでは、ルートノードにそれぞれ配列の最小要素と最大要素が含まれることはすでに説明しました。ヒープソートでは、ヒープのルート要素（最小または最大）が削除され、ソートされた配列に移動されます。次に、残りのヒープは、ヒーププロパティを維持するためにヒープ化されます。
したがって、ヒープソートを使用して特定の配列をソートするには、2つのステップを再帰的に実行する必要があります。
- 指定された配列からヒープを構築します。
- ルート要素をヒープから繰り返し削除し、並べ替えられた配列に移動します。残りのヒープをヒープ化します。
ヒープソートの時間計算量は、すべての場合でO（n log n）です。スペースの複雑さはO（1）です。
Javaのヒープソートアルゴリズム
以下に示すのは、指定された配列を昇順および降順でソートするためのヒープソートアルゴリズムです。
＃1）昇順でソートするヒープソートアルゴリズム：
- ソートする特定の配列の最大ヒープを作成します。
- ルート（入力配列の最大値）を削除し、ソートされた配列に移動します。配列の最後の要素をルートに配置します。
- ヒープの新しいルートをヒープ化します。
- 配列全体がソートされるまで、手順1と2を繰り返します。
＃2）降順でソートするヒープソートアルゴリズム：
- 指定された配列の最小ヒープを作成します。
- ルート（配列の最小値）を削除し、配列の最後の要素と交換します。
- ヒープの新しいルートをヒープ化します。
- 配列全体がソートされるまで、手順1と2を繰り返します。
Javaでのヒープソートの実装
以下のJavaプログラムは、ヒープソートを使用して配列を昇順でソートします。このために、最初に最大ヒープを構築し、次に上記のアルゴリズムで指定されているようにルート要素を再帰的にスワップしてヒープ化します。
import java.util.*; class HeapSort{ public void heap_sort(int heap_Array()) { int heap_len = heap_Array.length; // construct max heap for (int i = heap_len / 2 - 1; i >= 0; i--) { heapify(heap_Array, heap_len, i); } // Heap sort for (int i = heap_len - 1; i >= 0; i--) { int temp = heap_Array(0); heap_Array(0) = heap_Array(i); heap_Array(i) = temp; // Heapify root element heapify(heap_Array, i, 0); } } void heapify(int heap_Array(), int n, int i) { // find largest value int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap_Array(largest)) largest = left; if (right heap_Array(largest)) largest = right; // recursively heapify and swap if root is not the largest if (largest != i) { int swap = heap_Array(i); heap_Array(i) = heap_Array(largest); heap_Array(largest) = swap; heapify(heap_Array, n, largest); } } } class Main{ public static void main(String args()) { //define input array and print it int heap_Array() = {6,2,9,4,10,15,1,13}; System.out.println('Input Array:' + Arrays.toString(heap_Array)); //call HeapSort method for given array HeapSort hs = new HeapSort(); hs.heap_sort(heap_Array); //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(heap_Array)); } } 出力：
ヒープソート手法の全体的な時間計算量はO（nlogn）です。ヒープ化手法の時間計算量はO（ログ）です。ヒープを構築する時間の複雑さはO（n）です。
Javaでのスタックとヒープ
次に、スタックデータ構造とヒープの違いのいくつかを表にまとめましょう。
スタック ヒープ スタックは線形データ構造です。 ヒープは階層的なデータ構造です。 LIFO（後入れ先出し）の注文に従います。 トラバーサルはレベル順になっています。 主に静的メモリ割り当てに使用されます。 動的メモリ割り当てに使用されます。 メモリは連続して割り当てられます。 メモリはランダムな場所に割り当てられます。 スタックサイズは、オペレーティングシステムによって制限されます。 オペレーティングシステムによって適用されるヒープサイズに制限はありません。 スタックはローカル変数にのみアクセスできます。 ヒープにはグローバル変数が割り当てられています。 メモリの割り当て/割り当て解除は自動的に行われます。 割り当て/割り当て解除は、プログラマーが手動で行う必要があります。 スタックは、配列、リンクリスト、ArrayListなど、またはその他の線形データ構造を使用して実装できます。 ヒープは、配列またはツリーを使用して実装されます。 少ない場合はメンテナンスのコスト。 維持するのにより多くの費用がかかります。 メモリが限られているため、メモリが不足する可能性があります。 メモリの不足はありませんが、メモリの断片化に悩まされる可能性があります。
よくある質問
Q＃1）スタックはヒープよりも高速ですか？
回答： アクセスはヒープと比較してスタック内で線形であるため、スタックはヒープよりも高速です。
Q＃2）ヒープは何に使用されますか？
回答： ヒープは主に、ダイクストラのアルゴリズムのように2点間の最小または最短パスを見つけるアルゴリズム、ヒープソートを使用したソート、優先度付きキューの実装（min-heap）などで使用されます。
Q＃3）ヒープとは何ですか？その種類は何ですか？
回答： ヒープは、階層的なツリーベースのデータ構造です。ヒープは完全な二分木です。ヒープには2つのタイプがあります。つまり、ルートノードがすべてのノードの中で最大である最大ヒープです。ルートノードがすべてのキーの中で最小または最小である最小ヒープ。
Q＃4）スタックに対するヒープの利点は何ですか？
回答： スタックに対するヒープの主な利点はヒープにあり、メモリは動的に割り当てられるため、使用できるメモリの量に制限はありません。次に、スタックに割り当てることができるのはローカル変数のみですが、ヒープに割り当てることもできます。
Q＃5）ヒープに重複を含めることはできますか？
回答： はい。ヒープは完全なバイナリツリーであり、バイナリ検索ツリーのプロパティを満たさないため、ヒープ内に重複キーを持つノードを含めることに制限はありません。
結論
このチュートリアルでは、ヒープのタイプと、ヒープのタイプを使用したヒープソートについて説明しました。また、Javaでのその型の詳細な実装も確認しました。
=> ここで完璧なJavaトレーニングガイドをチェックしてください。
推奨読書
