ヒープデータ構造：ヒープとは何か？

ヒープデータ構造とは何ですか？

ヒープは、特殊なツリー型データ構造です。ヒープデータ構造は、ルート（親）と呼ばれる最上位ノードで構成されます。2番目のノードはルートの左の子、3番目のノードはルートの右の子です。ノードは左から右へと順にデータが格納されていきます。親ノードのキーは子ノードのキーと比較され、適切な配置が行われます。ツリー構造は視覚的に理解しやすく、各要素はノードと呼ばれ、各ノードには識別用の一意のキーが割り当てられています。

簡単に言うと、ヒープとはヒープ特性を満たす完全二分木のことです。つまり、すべての親要素は子要素に対して一貫した順序で並べられているため、優先度付きキューやヒープソートに最適です。

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

ヒープを使用する主な理由は以下のとおりです。

• ヒープデータ構造では、削除と挿入を対数時間で行うことができます – O(log₂n）。
• ツリー内のデータは特定の順序で配置されています。プログラマーは、最大値や最小値などの値を更新したり照会したりするだけでなく、親と子の間の関係を見つけることもできます。
• の概念を適用できます。 ドキュメントオブジェクトモデル ヒープデータ構造を視覚的に理解するのに役立ちます。
• ヒープは効率的な優先度付きキュー操作をサポートしており、これはダイクストラの最短経路法やプリムの最小全域木法といったグラフアルゴリズムにとって非常に重要です。

ヒープの種類

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

• 優先キュー: それはアブソリュートですtrac優先順位付けされたオブジェクトを含むデータ構造。各オブジェクトまたはアイテムには、あらかじめ優先順位が設定されています。したがって、優先順位の高いオブジェクトまたはアイテムが、他のオブジェクトまたはアイテムよりも先にサービスを受けます。
• バイナリヒープ: バイナリヒープは、削除や挿入といった単純なヒープ操作に適しています。ほとんどの標準ライブラリの優先度付きキューのデフォルトの実装として採用されています。
• 二項ヒープ: 二項ヒープは、ヒープを構成する一連の二項ツリーの集合から成ります。二項ヒープツリーは厳密に定義されているため、通常のツリーとは異なります。二項ツリー内の要素の総数は常に2に等しくなります。ⁿ ノード。
• ヒープソート: ほとんどのソートアルゴリズムとは異なり、ヒープソートはソート操作にO(1)の空間を使用します。これは比較に基づくソートアルゴリズムであり、まず入力を最大ヒープに変換することで昇順にソートを行います。ヒープソートは、改良された二分探索木と考えることができます。

通常、ヒープデータ構造は2つの戦略を採用します。入力が12-8-4-2と1の場合：

• 最小ヒープ – 最も価値が低いのは上部
• 最大ヒープ – 最も高い値が最上位

最小ヒープ

最小ヒープ構造では、ルートノードの値は、その子ノードの値以下になります。したがって、最小ヒープのルートは最小値を保持します。最小ヒープは完全二分木でもあります。

ツリー構造において最小ヒープが得られた時点で、すべての葉ノードが最大値の候補となります。ただし、正確な最大ヒープ値を求めるには、各葉ノードを個別に調べる必要があります。

最小ヒープの例

上の図を見ると、ルートから最下位のノードまで明確な順序があることがわかります。

配列Array_N[12, 2, 8, 1, 4]に要素を格納するとします。配列からわかるように、ルート要素は最小ヒープの優先順位に違反しています。最小ヒープの特性を維持するには、最小ヒープのルールが満たされるまで要素を交換する最小ヒープ化操作を実行する必要があります。

最大ヒープ

最大ヒープ構造では、親ノード（ルートノード）の値は、子ノードの値以上になります。このノードは最大値を保持します。最大ヒープは完全二分木であるため、値の集合からO(n)の時間で構築できます。

実装時によく使用される方法をいくつか紹介します Java 最大ヒープ:

• 追加 （）： ヒープに新しい要素を配置します。配列を使用する場合、オブジェクトは配列の末尾に追加されますが、二分木の場合は、オブジェクトは上から下、次に左から右の順に追加されます。
• 取り除く （）： この方法を使うと、配列リストから最初の要素を削除できます。新しく昇格した要素はもはや最大ではなくなるため、シフトダウン法は常にその要素を新しい位置に移動させます。
• シフトダウン（）： このメソッドは、ルートオブジェクトをその子オブジェクトと比較し、移動したノードを正しい位置に移動します。
• ふるい上げ（）： 配列メソッドを使用して配列に新しい要素を追加する場合、Sift-Upメソッドは、新しく追加されたノードを正しい位置に移動させるのに役立ちます。新しい項目は、まずツリーデータ構造をシミュレートすることで、その親要素と比較されます。

  親インデックス = 子インデックス / 2 という式を適用します。最大要素が配列の先頭に来るまで、この操作を繰り返します。

基本ヒープ Operaン

データセット内の最大値と最小値を見つけるには、検索、挿入、削除などの基本的なヒープ操作が必要です。要素は常に追加および削除されるため、次の操作方法を知っておく必要があります。

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

ヒープの作成

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

それでは、ウィリアムズの方法を用いて、12、2、8、1、4という値を挿入して最小ヒープの構築を始めましょう。空のヒープから始めて、他の要素を順次追加していくことで、n個の要素を持つヒープをO(n log n)の時間で構築できます。

• ヒープ化: ヒープの特性を維持しながら要素をヒープに挿入するのに役立つ挿入ルーチン。

  例えば、max-heapify操作では、親の値が子の値より大きいかどうかをチェックします。その後、要素はswapなどのメソッドを使用してソートできます。ping.

• マージ： 2つのヒープを1つに結合する場合は、マージ操作を使用して2つのヒープの値を統合します。元のヒープはそのまま保持されます。

ヒープの検査

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

要素をソートまたはキューに入れる際には、ヒープの状態を確認することが重要です。Is-Empty() を使用して処理対象の要素が存在するかどうかを確認することも重要です。ヒープのサイズは最大ヒープまたは最小ヒープのルートを特定するのに役立つため、ヒーププロパティに従う要素の数を把握する必要があります。

• サイズ – ヒープの大きさまたは長さを返します。ソートされた順序で格納されている要素の数を示します。
• 空です ヒープがnullの場合はTRUEを返し、それ以外の場合はFALSEを返します。

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

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

ヒープ データ構造の使用

ヒープデータ構造は、実生活における多くのプログラミングアプリケーションで役立ちます。例えば、以下のようなものです。

• スパムフィルタリングに役立ちます。
• ダイクストラ法やプリム法などのグラフアルゴリズムを実装する。
• Operaシステム負荷分散とデータ圧縮。
• k番目に小さい要素などの順序統計量を求める。
• 優先度付きキューを実装することで、リスト内の項目を対数時間で検索できるようになります。
• ヒープデータ構造は、ヒープソートによるソートにも使用されます。
• 待ち行列に並ぶ顧客をシミュレーションする。
• 割り込み処理 オペレーティングシステム.
• データ圧縮のためのハフマン符号化において。
• AI経路計画における最良優先探索とA*ヒューリスティクスの強化。

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

以下の特性は、ヒープ上に構築された優先度キューの動作を説明しています。

• 優先度ヒープでは、リスト内のデータ項目が互いに比較され、小さい要素または大きい要素が決定されます。
• 要素はキューに入れられ、その後、優先順位に従って削除されます。
• 優先度キュー内のすべての要素には、優先度として識別される固有の番号が割り当てられています。
• 優先度キューから出る際、最優先度の要素が最初に出る。

ヒープ優先度キューを実装するための手順 Java

次のセクションはコンクリートに移ります Java これらのルールを動作するコードに変換する実装。

ヒープソート Java 　 Code 例:

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 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 　 Code 例:

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]

次に、 二等分法.

よくあるご質問