1. 概要

このチュートリアルでは、最小ヒープベースの優先度キューのキーを減らす操作を紹介します。

まず、最小ヒープの使用法とアイデアを確認します。

次に、基本操作の更新を実装します。 その後、キーの減少操作を実装します。

2. 最小ヒープの背景

2.1. 最小ヒープ使用量

最小ヒープデータ構造は、次の2種類の操作を処理するために使用されます。

  1. データ構造に新しいキーを挿入します。 この操作の時間計算量はです。ここで、はヒープ内のキーの数です。
  2. データ構造から最小値のキーを抽出し、削除します。 同様に、この操作の時間計算量もです。ここで、はヒープ内のキーの数です。

このチュートリアルでは、decrease-key と呼ばれる3番目の操作を紹介します。これにより、データ構造内の特定のキーの値を減らすことができます。 主に、ダイクストラのアルゴリズムでは、特定のノードへの新しいパスを低コストで発見するときに、キーの減少操作が使用されます。

2.2. 最小ヒープデータ構造

まず、ヒープデータ構造は完全な二分木です。 したがって、最小ヒープデータ構造は完全なバイナリツリーであり、各ノードの値はその子よりも小さくなります。 したがって、各ノードの値はその親よりも大きくなります。

最小ヒープの例を見てください。

ご覧のとおり、各キーは子よりも小さく、親よりも大きくなっています。 したがって、最小値は常にツリーのルートになります。 ただし、ヒープデータ構造を完全なバイナリツリーに格納するのは複雑です。 したがって、配列を使用して格納します。

まず、ルートの値をインデックス1に格納します。 次に、左の子をインデックス2に格納し、右の子をインデックス3に格納します。 一般に、ノードをインデックスに格納した場合、左の子をインデックスに格納し、右の子をインデックスに格納します。

以前に提供したヒープの例を保存する方法を見てみましょう。

i番目のノードの親はインデックスにあることに注意してください。 親のインデックスは、ノードのインデックスを2で除算することによって取得されることに注意してください。除算のモジュロは、破棄されます。

たとえば、値2のノードをインデックス3に格納しました。 したがって、値9の左の子をインデックスに格納しました。 また、値3の右の子をインデックスに格納しました。 さらに、この場合はルートである親をインデックスに格納しました。

3. 必要な更新

最小ヒープ内の特定のキーの値を減らすには、最初にこのキーに到達する必要があります。 通常のヒープでは、ヒープ内の特定のキーを検索することはできません。

したがって、元の配列の横にマップデータ構造を保持します。 このマップは、ヒープ内の各キーのインデックスを格納します。 したがって、ヒープ内の特定のキーにアクセスする必要がある場合は、このマップを使用してそのインデックスを決定します。

基本的なヒープ操作に必要な更新について説明しましょう。

3.1. スワップ

ヒープに値を挿入または抽出する場合、通常、一連のスワップを実行します。 これらのスワップの理由は、後で説明するように、キーを正しい場所に配置するためです。

配列の2つのインデックスを取得し、それらの値を交換するスワップ関数を実装しましょう。

まず、インデックスとの内部の値を交換します。 次に、マップ内のこれらの値のインデックスを更新します。 ハッシュマップを使用した場合、この関数は時間計算量で実装できます。

3.2. 入れる

最小ヒープに新しいキーを挿入するときは、それが完全なツリーであるという考えを維持する必要があります。 したがって、配列の最後にキーを挿入します。 その後、必要なだけキーを上に移動します。

更新された挿入操作を見てください。

最初に、配列の最後に新しいキーを挿入します。 次に、このキーのインデックスをマップ内に保存します。

その後、挿入されたキーから複数のステップを実行します。 各ステップで、キーの値をその親の値と比較します。 このキーの値が親よりも小さい場合は、アルゴリズム1の関数を使用して値を交換します。 これらの手順は、ルートに到達するか、キーが親よりも小さくなるまで続きます。

挿入操作の複雑さは以前と同じです。ここで、はヒープ内のキーの数です。

3.3. エキス

ヒープからキーを抽出するときは、それが完全な二分木であるという考えも維持する必要があります。 したがって、ルートの代わりにヒープ内に最後のキーを配置します。 その後、このキーを必要なだけ下に移動し続けます。

抽出操作を見てみましょう。

まず、返される値を保存し、マップから削除します。 次に、ヒープを完全な状態に保つために、ルートの場所に最後のキーを配置し、マップ内のインデックスを更新します。

その後、ルートから複数のステップを実行します。 各ステップで、キーの値をその子間の最小値と比較します。 キーの値がその子の最小値よりも大きい場合、アルゴリズム1の関数を使用してこれら2つのキーを交換します。 それ以外の場合は、whileループを中断します。

最後に、最初に保存した値を返します。

抽出操作の複雑さは以前と同じです。ここで、はヒープ内のキーの数です。

4. 減少キー

特定のキーの値を減らすために、マップを使用してそのインデックスを見つけます。 インデックスを見つけたら、値を変更し、必要に応じてツリーの上方に移動し始めます。 キーをツリーの上方に移動する理由は、その値が減少したためです。 したがって、その場所にとどまるか、上に移動します。

キーの減少操作を調べてみましょう。

まず、マップを使用して、指定されたキーのインデックスを見つけます。 次に、キーの古い値をマップから削除して減らし、新しい値をマップ内に保存します。

第三に、キーのインデックスから開始して複数のステップを実行します。 各ステップで、キーの値をその親の値と比較します。 キーの値がその親の値よりも小さい場合、アルゴリズム1の関数を使用してそれらの値を交換します。

ルートに到達するか、親の値がキーの値よりも小さい場所に到達すると、whileループを中断します。

減少操作の複雑さはです。ここで、はヒープ内のキーの数です。

5. 結論

このチュートリアルでは、最小ヒープのキーの減少操作を示しました。 最初に、最小ヒープの基本概念について説明しました。 次に、基本的な操作に必要な更新について説明しました。

第三に、キー減少操作を実装しました。