この記事では、ヒープソートの動作の完全な概要を説明し、後でJavaでバイナリヒープを実装する方法を学習します。
Javaでパワーを使用する方法
この記事の議題は次のとおりです。
- ヒープソートとは何ですか?
- 最大ヒープ
- 最小ヒープ
- Javaでのヒープの実装
- ダイアグラム
- コード
さぁ、始めよう!
ヒープソートとは何ですか?
ヒープは基本的にツリーベースのデータ構造です。ノードがあります。ノードは特定の要素で構成されます。すべてのノードには1つの要素が含まれています。
ノードには子がある場合があります。子供がいない場合はリーフと呼ばれます。
従うべき2つのルールがあります:
- すべてのノードの値は、その子に格納されているすべての値以下である必要があります。
- 高さは可能な限り低くなっています。
ヒープは、抽出に非常に効率的です最小または最大の要素。
さあ、最小ヒープに移りましょう!
最小ヒープ
最小ヒープは、ルート要素の値が子要素のいずれか以下である完全な二分木です。
最小ヒープの表現
Arr [(i-1)/ 2]: これにより、親ノードが返されます。
Arr [(2 * i)+ 1]: これにより、左側の子ノードが返されます。
Arr [(2 * i)+ 2]: これにより、正しい子ノードが返されます。
最小ヒープには特定の方法があります。
- インサート(): ツリーの最後に新しいキーが追加されます。新しいキーが親よりも大きい場合は、何もする必要はありません。それ以外の場合は、ヒーププロパティを設定するためにトラバースする必要があります。
- getMin(): このメソッドは、ルート要素を返すのに役立ちます。
- extractMin(): このメソッドは最小値を返します素子。
今すぐMaxヒープに移動します。
最大ヒープ
最大ヒープは、ルート要素の値が子要素のいずれか以上である完全な二分木です。
最大ヒープもいくつかの方法で構成されています!
- 挿入(): ヒープに要素を挿入します。
- Delete() :ヒープから要素を削除します。
- FindMax(): ヒープから最大の要素を見つけます。
- printHeap(): ヒープの内容を出力します
ここで、ヒープの実装を図と後でJavaで示します。コード。
Javaでのヒープの実装
図:
上の図は、Javaのバイナリヒープを示しています。最小ヒープと最大ヒープの2つのヒープがあることを学習したので、次の図を示します。
次のセグメントに移り、Javaでバイナリヒープを実装する方法を見ていきます。
コード:
public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** *これにより、ヒープがデフォルトサイズで初期化されます。 * / public BinaryHeap(intcapacity){heapSize = 0 heap = new int [capacity + 1] Arrays.fill(heap、-1)} / ** *これは、ヒープが空かどうかをチェックします*複雑さ:O( 1)* / public boolean isEmpty(){return heapSize == 0} / ** *これはヒープがいっぱいかどうかをチェックします*複雑さ:O(1)* / public boolean isFull(){return heapSize == heap .length} private int parent(int i){return(i-1)/ d} private int kthChild(int i、int k){return d * i + k} / ***これにより新しい要素がヒープに挿入されます*複雑さ:O(log N)*最悪のシナリオとして、ルートまでトラバースする必要があります* / public void insert(int x){if(isFull())throw new NoSuchElementException( 'ヒープがいっぱいです、挿入するスペースがありませんnew element ')heap [heapSize ++] = x heapifyUp(heapSize-1)} / ** *これによりインデックスxの要素が削除されます*複雑さ:O(log N)* * / 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)retu rn key} / ** *このメソッドは、要素の挿入中にヒーププロパティを維持するために使用されます。 * * / 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} / ** *このメソッドは、要素の削除中にヒーププロパティを維持するために使用されます。 * * / private void heapifyDown(int i){int child int temp = heap [i] while(kthChild(i、1)heap [rightChild]?leftChild:rightChild} / ***このメソッドはヒープのすべての要素を出力するために使用されます** / public void printHeap(){System.out.print( 'nHeap =')for(int i = 0 i これで、Javaのバイナリヒープに関するこの記事は終わりです。 チェックしてください 25万人以上の満足した学習者のネットワークを持つ信頼できるオンライン学習会社であるEdurekaが世界中に広がっています。 EdurekaのJavaJ2EEおよびSOAトレーニングおよび認定コースは、Java開発者になりたい学生および専門家向けに設計されています。このコースは、Javaプログラミングをすぐに開始できるように設計されており、HibernateやSpringなどのさまざまなJavaフレームワークに加えて、コアと高度なJavaの両方の概念についてトレーニングします。
質問がありますか?この「JavaArrayList」ブログのコメントセクションでそれについて言及してください。できるだけ早くご連絡いたします。