技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

ヒープ

ヒープと優先キュー:

プライオリティ キューは抽象データ型であり、ヒープはデータ構造であるため、ヒープはプライオリティ キューを実装する方法ではありません。
優先キューを実装するには、配列やリンク リストなど、さまざまな方法があります。ただし、これらの実装では、挿入操作と削除操作の 1 つが O(1)O(1) 時間の計算量で完了できることのみを保証できますが、もう 1 つの操作は O(N)O(N) 時間以内に完了する必要があります。時間の複雑さ。ヒープにより、優先キューの挿入操作は時間計算量 O(log N)O(logN) 以内に完了し、削除操作は時間計算量 O(log N)O(logN) 以内に完了できます。 。

ヒープは、次の条件を満たす特別なバイナリ ツリーです。

1. 完全なバイナリ ツリー (ノードは左から右の順序で配置されます)。
2. 各ノードの値は、その子ノードの値以上、またはそれ以下でなければなりません。

ヒープの特徴:

1. 要素は O(logN) の時間計算量でヒープに挿入できます。
2. 要素は O(logN) 時間の計算量でヒープから削除できます。
3. ヒープ内の最大値または最小値は、O(1) 時間計算量内で取得できます。

ヒープの分類:

最大ヒープ: ヒープ内の各ノードの値は、その子ノードの値以上です。最大ヒープの最上位要素 (ルート ノード) は、ヒープ内の最大値です。
最小ヒープ: ヒープ内の各ノードの値は、その子ノードの値以下です。最小ヒープの最上位要素 (ルート ノード) は、ヒープ内の最小値です。
現在のノード番号は i で、左の子の番号は 2i、右の子の番号は 2i+1 です。

時間の複雑さと空間の複雑さ

ヒープソート

理論: ヒープ ソートとは、ヒープのデータ構造を使用して、順序付けされていない要素のセットをソートすることを指します。

最小ヒープ ソート アルゴリズムの手順は次のとおりです。

すべての要素を最小ヒープにヒープします。
ヒープの最上位要素を取り出して削除し、順序付けられた要素を格納するデータ セット T にヒープの最上位要素を配置します。
この時点で、ヒープは新しい最小ヒープに調整されます。
ヒープ内に要素がなくなるまで手順 3 と 4 を繰り返します。
このとき、要素が小さいものから大きいものへと順番に並べられた新たなデータ集合Ｔが得られる。

最大ヒープ ソート アルゴリズムの手順は次のとおりです。

すべての要素を最大ヒープにヒープします。
ヒープの最上位要素を取り出して削除し、順序付けられた要素を格納するデータ セット T にヒープの最上位要素を配置します。
この時点で、ヒープは新しい最大ヒープに調整されます。
ヒープ内に要素がなくなるまで手順 3 と 4 を繰り返します。
このとき、要素が大きいものから小さいものへと順に並べられた新たなデータ集合Ｔが得られる。
時間計算量: O(Nlog N)。 N はヒープ内の要素の数です。

空間の複雑さ: O(N)。 N はヒープ内の要素の数です。