AF-heap とは

コンピュータ科学では、AFヒープは整数データの優先キューの一種であり、M. L. FredmanとD. E. Willardによって提案されたアトムヒープを使用する融合ツリーの拡張です。
AFヒープを使用すると、時刻O(m + n log n / log log n)の機械整数キーに対してm個の挿入または減少キー操作およびn delete-min操作を実行することが可能です。これにより、Dijkstraのアルゴリズムは、n個のエッジとm個の頂点を持つグラフ上の同じO(m + n log n / log log n)時間に実行され、最小スパニングツリーに対して線形時間アルゴリズムが導き出されます。入力グラフのエッジ重みが経粘膜モデルの機械整数であるという問題。

Bucket queue とは

データ構造の設計および分析では、バケット・キュー(バケット優先順位キューまたは有界高優先順位キューとも呼ばれる)は、優先順位が小さい整数である要素を優先順位付けする優先順位キューです。それはバケットの配列の形をしています:配列データ構造は優先順位によってインデックス付けされ、そのセルには互いに同じ優先順位の項目のバケットが含まれています。
バケットキューは、ハッシュソートソート(バケットソートとも呼ばれます)のプライオリティキューアナログです。ソートアルゴリズムは、要素を優先順位によってインデックス付けされたバケットに配置し、バケットを連結します。選択ソートで優先度キューとしてバケット・キューを使用すると、ピジョンホール・ソート・アルゴリズムの形式が得られます。
バケットキューのアプリケーションには、グラフの縮退の計算と、最短パスの高速アルゴリズムと、小さな整数または既にソートされているウェイトを持つグラフの最も広いパスが含まれます。その最初の使用はDial(1969)の最短経路アルゴリズムであった。

Min-max heap とは

コンピュータサイエンスでは、min-maxヒープは、min-heapとmax-heapの両方の有用性を組み合わせた完全なバイナリツリーデータ構造です。つまり、最小時間と最大時間の一定時間の検索と対数時間の削除を提供しますその中の要素。これにより、min-maxヒープは両端の優先順位キューを実装するための非常に有用なデータ構造になります。バイナリのmin-heapsやmax-heapsのように、min-maxヒープは対数の挿入と削除をサポートし、線形時間で構築することができます。最小最大ヒープは、しばしば暗黙的に配列内に表現されます。したがって、暗黙のデータ構造と呼ばれています。
最小最大ヒーププロパティは次のとおりです。ツリー内の偶数レベルの各ノードはその子孫のすべてよりも小さく、ツリー内の奇数レベルの各ノードはその子孫のすべてよりも大きい。
find-median、delete-median、find(k)(構造内のk番目の最小値の決定)、operation delete(k)(k番目のものを削除するなど、他の順序統計操作を効率的にサポートするように構造を一般化することもできます。構造の最小値)、kの任意の固定値(または値の集合)に対してこれらの最後の2つの演算は、それぞれ一定の時間および対数の時間で実施することができる。 min-max順序付けの概念は、左または右の木などの最大または最小順序に基づいて他の構造に拡張して、新しい(そしてより強力な)クラスのデータ構造を生成することができます。 min-maxヒープは、外部クイックソートを実装するときにも役立ちます。

Skew binomial heap とは

コンピュータ科学では、スキュー二項ヒープ(またはスキュー二項行列)は、元の二項ヒープからの最悪ケースのO(log n)挿入ではなく、最悪ケースのO(1)挿入をサポートする二項ヒープの変形です。二項数ヒープは二進数システムに基づいているのと同様に、二進ヒープスキューはスキュー二進数システムに基づいています。

Randomized meldable heap とは

コンピュータサイエンスでは、ランダム化された融合可能ヒープ(Meldable HeapまたはRandomized Meldable Priority Queue)が優先順位キューベースのデータ構造であり、その基礎構造もヒープ順のバイナリツリーです。ただし、基本となるバイナリツリーの形状に制限はありません。
このアプローチには、同様のデータ構造に比べて多くの利点があります。ランダム化された融合可能なヒープのすべての操作は実装が簡単で、複雑さの境界内の定数は小さいです。また、バランス条件を維持する必要もなく、ノード内の衛星情報は必要ない。最後に、この構造は良好な最悪の場合の時間効率を有する。各個々の操作の実行時間は、多くの場合、高い確率で対数である。

Double-ended priority queue とは

コンピュータサイエンスでは、ダブルエンド優先順位キュー(DEPQ)またはダブルエンドヒープは、優先順位キューまたはヒープと同様のデータ構造ですが、キーの順序によっては最大値と最小値の両方を効率的に削除できます(アイテム)を格納します。 DEPQのすべての要素に優先順位または値があります。 DEPQでは、昇順と降順の両方で要素を削除することができます。

Van Emde Boas tree とは

vEBツリーとも呼ばれるVan Emde Boasツリー(またはVan Emde Boas優先キュー、オランダの発音:[vɑn 'ɛmdə'boːɑs])は、mビットの整数キーを持つ連想配列を実装するツリーデータ構造です。これは、O(ログm)時間、またはO(ログログM)時間ですべての操作を実行します。ここで、M = 2mはツリーに格納できる要素の最大数です。 Mはツリーに格納されている要素の実際の数と混同してはなりません。これにより他のツリーデータ構造のパフォーマンスが測定されることがよくあります。 vEBツリーは、以下に説明するように、多数の要素を含む場合、良好な空間効率を有する。それは、1975年にオランダのコンピュータ科学者Peter van Emde Boasが率いるチームによって発明されました。

Pagoda (data structure) とは

コンピュータサイエンスでは、パゴダはバイナリツリーの変形で実装された優先キューです。ルートは、バイナリツリーのように、その子を指します。他のすべてのノードは、その親を指し、左端(右の子であれば)または右端(左の子であれば)の子孫の葉までを指します。基本的な操作は、ヒーププロパティを維持するmergeまたはmeldです。要素をシングルトンとしてマージして挿入します。ルートは、その右と左の子をマージすることによって削除されます。マージはボトムアップで、1つの左端を他の端の右端にマージします。

Kinetic priority queue とは

キネティック優先度キューは、抽象的なキネティックデータ構造である。これは、すべての要素の優先順位が時間の連続関数として変化しているときに、最大(または最小)優先順位要素(キー値ペア)を維持するように設計された優先順位キューの変形です。動力学的優先度待ち行列は、いくつかの動力学的データ構造の構成要素として使用されているだけでなく、k-set問題および連結された赤青色セグメント交差問題などのいくつかの重要な非運動問題を解決する。

Leftist tree とは

コンピュータサイエンスでは、左ツリーまたは左ヒープは、バイナリヒープの変形で実装された優先キューです。すべてのノードには、最も近いリーフまでの距離であるs値があります。バイナリヒープとは対照的に、左木は非常に不均衡になります。ヒーププロパティに加えて、各ノードの右の子孫がより低いs値を持つように、左ツリーが維持されます。
高さに偏った左翼の木は、クラーク・アラン・クレーンによって考案されました。名前は、通常、左のサブツリーが右のサブツリーよりも背が高いという事実から来ています。
左翼の木は合併可能なヒープです。新しいノードをツリーに挿入すると、新しい1ノードのツリーが作成され、既存のツリーにマージされます。アイテムを削除するには、そのアイテムを左右のサブツリーのマージに置き換えます。これらの操作は両方ともO(log n)時間かかる。挿入の場合、これはO(1)(定数)償却時間とO(log n)ワーストケースでの挿入をサポートするフィボナッチヒープよりも遅いです。
左木は、Θ(n)を取るバイナリヒープに比べて、すぐにマージする能力があるので、有利です。ほとんどの場合、スキューヒープのマージによってパフォーマンスが向上します。しかし、左ヒープをマージすると最悪の場合のO(log n)複雑さがあり、スキューヒープをマージするとO(log n)の複雑さは償却されます。