ヒープデータ構造: ヒープとは何ですか? 最小および最大ヒープ (例)

ヒープとは何ですか?

ヒープは特殊なツリーデータ構造です。ヒープは、ルート (親) と呼ばれる最上位ノードで構成されます。2 番目の子はルートの左の子、3 番目のノードはルートの右の子です。後続のノードは左から右に埋められます。親ノードのキーは子ノードのキーと比較され、適切な配置が行われます。各エンティティがノードと呼ばれるツリーは簡単に視覚化できます。ノードには識別用の一意のキーがあります。

なぜヒープデータ構造が必要なのでしょうか?

ヒープデータ構造を使用する主な理由は次のとおりです。

ヒープデータ構造により、対数時間 – O(log) での削除と挿入が可能になります。₂n）。
ツリー内のデータは特定の順序で作成されます。プログラマは、最大値や最小値などを更新したりクエリしたりするだけでなく、親と子の関係を見つけることもできます。
の概念を適用できます。ドキュメントオブジェクトモデルヒープデータ構造を理解するのに役立ちます。

ヒープの種類

ヒープデータ構造には、優先キュー、バイナリヒープ、二項ヒープなど、ヒープデータ構造内の要素の挿入と削除を処理するためのさまざまなアルゴリズムがあります。ヒープソート.

優先キュー: これは、優先順位付けされたオブジェクトを含む抽象データ構造です。各オブジェクトまたはアイテムには、事前に設定された優先順位があります。したがって、より高い優先度が割り当てられたオブジェクトまたはアイテムが、残りよりも先にサービスを受けます。
バイナリヒープ: バイナリヒープは、削除や挿入などの単純なヒープ操作に適しています。
二項ヒープ: 二項ヒープは、ヒープを構成する二項ツリーの一連のコレクションで構成されます。二項ヒープツリーは厳密に定義されているため、通常のツリーではありません。二項ツリー内の要素の総数は常に 2 になります。ⁿ ノード。
ヒープソート: ほとんどのソートアルゴリズムとは異なり、ヒープソートはソート操作に O(1) のスペースを使用します。これは比較ベースのソートアルゴリズムであり、最初に最大ヒープに変換してから昇順でソートします。ヒープソートは、品質が向上したバイナリ検索ツリーとして考えることができます。

通常、ヒープデータ構造では 12 つの戦略が使用されます。入力8 – 4 – 2 – 1およびXNUMXの場合

最小ヒープ – 上部の最小値
最大ヒープ – 上部の最大値

最小ヒープ

Min Heap 構造では、ルートノードの値は、そのノードの子ノードと同じかそれより小さくなります。 Min Heap のこのヒープノードは最小値を保持します。全体として、その最小ヒープ構造は完全です。二分木.

ツリーに Min ヒープを作成したら、すべての葉が有力な候補になります。ただし、正確な Max-heap 値を取得するには、各リーフを調べる必要があります。

最小ヒープの例

上の図では、ルートから最下位ノードまでの明確なシーケンスに気づくことができます。

配列 Array_N[12,2,8,1,4] に要素を格納するとします。配列からわかるように、ルート要素は Min Heap 優先度に違反しています。Min heap プロパティを維持するには、min-heapify 操作を実行して、Min heap プロパティが満たされるまで要素を入れ替える必要があります。

最大ヒープ

Max Heap の構造では、親ノードまたはルートノードは、ノード内のその子ノードと同じかそれより大きな値を持ちます。このノードは最大値を保持します。さらに、これは完全なバイナリツリーなので、値のコレクションから最大ヒープを構築し、O(n) 回で実行できます。

Java max ヒープを実装するためのいくつかの方法を次に示します。

追加（）: 新しい要素をヒープに配置します。配列を使用する場合、オブジェクトは配列の最後に追加されますが、バイナリツリーでは、オブジェクトは上から下に追加され、その後、左から右に追加されます。
取り除く（）: このメソッドを使用すると、配列リストから最初の要素を削除できます。新しく追加された要素は最大ではないため、Sift-Down メソッドは常にそれを新しい場所にプッシュします。
シフトダウン ()このメソッドは、ルートオブジェクトをその子と比較し、新しく追加されたノードを適切な位置にプッシュします。
シフトアップ (): 配列メソッドを使用して新しく挿入された要素を配列に追加する場合、Sift-Up メソッドは新しく追加されたノードを新しい位置に再配置するのに役立ちます。新しく挿入された項目は、まずツリーデータ構造をシミュレートすることによって親と比較されます。
式 Parent_Index=Child_Index/2 を適用します。最大の要素が配列の先頭に来るまでこれを続けます。

基本ヒープ Operaン

データセット内の最高値と最低値を見つけるには、検索、削除、挿入などの基本的なヒープ操作を多数実行する必要があります。要素は絶えず追加、削除されるため、次の操作を行う必要があります。

もう完成させ、ワークスペースに掲示しましたか? – ヒープ内のアイテムを探します。
インセット – 新しい子をヒープに追加します。
削除 – ヒープからノードを削除します。

ヒープの作成

ヒープを構築するプロセスは、ヒープの作成と呼ばれます。キーのリストが与えられると、プログラマーは空のヒープを作成し、基本的なヒープ操作を使用して他のキーを 1 つずつ挿入します。

それでは、Willaim の方法を使用して値 12,2,8,1、4、XNUMX、XNUMX、および XNUMX をヒープに挿入して Min ヒープの構築を開始しましょう。 n 個の要素を含むヒープを構築するには、空のヒープから開始し、O (nlogn) 時間をかけて他の要素を連続的に埋め込みます。

Heapify: 挿入アルゴリズムで、ヒープに要素を挿入するのに役立ちます。強調表示されたプロパティヒープデータ構造に従っているかどうかをチェックします。
たとえば、最大ヒープ化は親の値が子の値より大きいかどうかをチェックします。その後、スワッピングなどの方法を使用して要素をソートできます。

マージ: XNUMX つのヒープを XNUMX つに結合することを考慮して、マージヒープを使用して XNUMX つのヒープの値を結合します。ただし、元のヒープはまだ保存されています。

ヒープの検査

ヒープの検査とは、ヒープデータ構造内の要素の数をチェックし、ヒープが空かどうかを検証することを指します。

ヒープを要素のソートやキューイングとして検査することが重要です。Is-Empty() を使用して処理する要素があるかどうかを確認することが重要です。ヒープサイズは、最大ヒープまたは最小ヒープを見つけるのに役立ちます。したがって、ヒーププロパティに続く要素を知っておく必要があります。

サイズ – ヒープの大きさまたは長さを返します。ソート順に要素がいくつあるかを確認できます。
空です – ヒープが NULL の場合は TRUE を返し、それ以外の場合は FALSE を返します。

ここでは、すべての要素を印刷しています。 優先度Q ループしてから、priorityQ が空でないことを確認します。

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

ヒープデータ構造の使用

ヒープデータ構造は、次のような現実の多くのプログラミングアプリケーションで役立ちます。

スパムフィルタリングに役立ちます。
グラフアルゴリズムの実装。
Operaシステムの負荷分散とデータ圧縮。
統計で順序を見つけます。
対数時間でリスト内の項目を検索できる優先キューを実装します。
ヒープデータ構造はソートにも使用されます。
回線上の顧客をシミュレートします。
割り込み処理オペレーティングシステム.
ハフマンのデータ圧縮コーディング。

ヒープ優先キューのプロパティ

優先度ヒープでは、リスト内のデータ項目が相互に比較されて、より小さい要素が決定されます。
要素はキューに配置され、その後削除されます。
優先度キュー内のすべての要素には、優先度として識別される要素に関連する一意の番号があります。
優先キューを出るときは、最優先の要素が最初に抜けます。

ヒープ優先キューを実装する手順 Java

コード例を使用した JAVA でのヒープソート

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

出力

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

ヒープソート Python コード例付き

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)

出力

[1, 3, 4, 7, 9]

次に、次について学びます。二等分法

まとめ

ヒープは特殊なツリーデータ構造です。親と子がいる家系図を想像してみましょう。
のヒープデータ構造 Java 対数時間での削除と挿入が可能 – O(log₂n）。
山積み Python ヒープデータ構造内の要素の挿入と削除を処理するためのさまざまなアルゴリズム (優先度キュー、バイナリヒープ、二項式ヒープ、ヒープソートなど) があります。
Min Heap 構造では、ルートノードの値はそのノードの子ノードと同じかそれより小さくなります。
Max Heap の構造では、ルートノード (親) はノード内の子と同じかそれより大きな値を持ちます。
ヒープの検査とは、ヒープデータ構造内の要素の数をチェックし、ヒープが空かどうかを検証することを指します。

よろしければ：