データ構造のインターバルヒープ
ここでは、間隔ヒープとは何かを確認します。間隔ヒープは完全な二分木であり、最後のノードを除く各ノードには2つの要素が含まれている可能性があります。ノードPの2つの要素の優先順位を「a」と「b」とします。ここでは、≤bを検討しています。ノードPは閉区間[a、b]を表すと言います。ここで、aはPの区間の左端であり、bは右端です。 [c、d]は、a≤c≤d≤bの場合に限り、区間[a、b]に含まれます。区間ヒープでは、各ノードPの左右の子で表される区間は、Pで表される区間に含まれます。最後のノードに優先度cの単一要素が含まれている場合、a≤c≤bです。ここで、[a、b]は最後のノードの親の間隔です。
これは、最小ヒープと最大ヒープで構成されます。最大ヒープと最小ヒープ。
これは最小ヒープです
これは最大ヒープです
-
データ構造における圧縮された四分木と八分木
圧縮された四分木 細分化されたセルに対応するすべてのノードを格納するときに、多くの空のノードを格納してしまう可能性があります。このようなまばらなツリーのサイズを縮小するには、葉に興味深いデータがあるサブツリー（つまり、「重要なサブツリー」）のみを保存します。ここでも、実際にサイズをさらに縮小することができます。重要なサブツリーのみを考慮する場合、プルーニングプロセスは、中間ノードの次数が2（1つの親と1つの子へのリンク）であるツリー内の長いパスを回避する場合があります。このパスの先頭にノードUを格納し（そして削除されたノードを表すためにいくつかのメタデータをそれに関連付けて）、その最後にルー
-
ハーフエッジデータ構造
はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ