KDヒープ

20 個の要素を持つ 2 次元ヒープ。

KDヒープ^[1] は、コンピュータサイエンスにおけるデータ構造であり、追加のスペースを必要とせずに多次元の優先キューを実装します。これはヒープ^[2]の一般化です。KDヒープは、k次元のいずれかにおいて、効率的な挿入、最小要素のクエリ、および最小要素の削除を可能にするため、両端ヒープを特別なケースとして含みます。

構造

それぞれにキー (または優先順位) があるn個のアイテムのコレクションが与えられると、 KD ヒープはそれらを2 つの条件を満たす バイナリ ツリーに整理します。${\displaystyle k}$

• これは完全な二分木です。つまり、最後の層を除いて完全に満たされており、最後の層は左から埋める必要があります。
• kd ヒープ順序を満たします。

kdヒープ順序の特性は、通常のヒープのヒープ特性と類似しています。ヒープがkdヒープ順序を維持するのは、以下の条件を満たす場合です。

• ルートノードはツリー全体の中で最小の第一特性を持ち、
• ルートではない他のすべてのノードv は、その親w が親をルートとするサブツリーの最小の i 番目のプロパティを持つ場合、vは vをルートとするサブツリー全体の最小の i 番目のプロパティを持つことになります。${\displaystyle (i\mod k)+1}$

この構造の 1 つの結果として、最小の 1 番目のプロパティ要素は当然ルートにあり、さらに、すべてのiに対するすべての最小のi番目のプロパティ要素は最初のkレベルにあることになります。

オペレーション

n個のアイテムから KD ヒープを作成するにはO(n) の時間がかかります。以下の操作がサポートされています。

• O(log n)の時間で新しいアイテムを挿入する
• 任意の次元で最小のキーを持つアイテムを定数時間で取得する
• 任意の次元で最小キーを持つアイテムをO(log n)の時間で削除します。
• ヒープ内の任意のアイテムを、その位置がわかっていると仮定して、O(log n)の時間で削除または変更する

重要なのは、これらの操作における隠れた定数は次元数に対して指数的に大きいため、KD ヒープは非常に多くの次元を持つアプリケーションには実用的ではないということです。 ${\displaystyle k}$

参考文献

1. Ding Y., Weiss MA (1993)「K -Dヒープ：効率的な多次元優先キュー」Dehne F., Sack JR., Santoro N., Whitesides S. (編)『アルゴリズムとデータ構造』WADS 1993. Lecture Notes in Computer Science, vol 709. Springer, Berlin, Heidelberg
2. 高度なデータ構造、ピーター・ブラス、ISBN 978-0-521-88037-4、270ページ