プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

ペアリングヒープの適応特性

ペアリングヒープは、優先キューを完全に使用するために実装されています。優先キューはオブジェクトのセットの最小値を追跡するため、キューから何かを削除するたびに、それは常に最小値になります。優先キューは主に、ダイクストラのアルゴリズムを使用してグラフ内の最短経路を計算するときに実装されます。

ペアリングヒープは、実際のアプリケーションで使いやすく、操作しやすいため、完璧です。具体的には、それらは償却時間で優れた動作をします。つまり、個々の操作はより長い時間を消費しますが、キューのライフサイクル全体にわたるすべての操作の合計は高速です。ペアリングヒープはコーディングが簡単で、多くの場合、フィボナッチヒープよりも適切に動作します。

ペアリングヒープには非常に単純なプロパティがあります。各ヒープは、オブジェクトまたは値に関連付けられています。各ヒープには、子ヒープのセットも装備されています。オブジェクトの値は、常にその子ヒープの値よりも大きい（または小さい）。

ヒープにはいくつかの基本的な操作があります-

min（heap） –最小値を取得します。この機能はとても簡単です。ヒープの最高値に見えます。

merge（heap1、heap2） –2つのヒープをマージまたは結合します。他のヒープの子に最大値のヒープを追加します。また、この機能は高速です。


  1. ペアリングヒープのバリエーション

    ペアリングヒープは、空のヒープ、またはルート要素とペアリングツリーの空のリストを含むペアリングツリーのいずれかです。 ヒープ順序プロパティでは、ノードの親がノード自体より大きくないことが必要です。 次の説明では、キーの減少操作をサポートしない純粋関数型ヒープについて検討します。 タイプPairingTree[Element]=Heap（element：Element、subheaps：List [PairingTree [Element]]） タイプPairingHeap[Element]=Empty | PairingTree [Element] ペアリングヒープには、最小ペアリ

  2. ペアリングヒープ

    ペアリングヒープは、実装が比較的簡単で、実用的な償却パフォーマンスが優れているヒープデータ構造の一種として定義されています。 ペアリングヒープは、ヒープ順に並べられたマルチウェイツリー構造であり、簡略化されたフィボナッチヒープとして表すことができます。 これらは、プリムのMSTアルゴリズムなどのアルゴリズムを実装するための「堅牢な選択」と見なされ、次の操作をサポートします（最小ヒープを想定）- find-min −この関数は、ヒープの最上位要素を返す役割を果たします。 溶ける -この関数は、2つのルート要素を比較する役割を果たします。結果のルートが小さいほど、大きい要素とそのサブツ