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

データ構造の最大ヒープからの削除

ここでは、バイナリ最大ヒープデータ構造から要素を削除する方法を説明します。最初のツリーが次のようになっていると仮定します-

データ構造の最大ヒープからの削除

削除アルゴリズム 
delete(heap, n) −
Begin
   if heap is empty, then exit
   else
      item := heap[1]
      last := heap[n]
      n := n – 1
      for i := 1, j := 2, j <= n, set i := j and j := j * 2, do
         if j < n, then
            if heap[j] < heap[j + 1], then j := j + 1
         end if
         if last >= heap[j], then break
         heap[i] := heap[j]
      done
   end if
   heap[i] := last
End

例

最後のヒープから30を削除したいとします-

データ構造の最大ヒープからの削除


  1. データ構造におけるBツリーの削除

    ここでは、Bツリーからノードを削除する方法を説明します。以下のようなBTreeがあるとします- Bツリーの例 − 削除には2つの部分があります。まず、要素を見つける必要があります。その戦略はクエリのようなものです。ここで削除するには、いくつかのルールに注意する必要があります。 1つのノードには少なくともm/2個の要素が必要です。したがって、1つの要素を削除し、残りの要素がm-1未満の場合、それ自体が調整されます。ノード全体が削除されると、その子がマージされ、それらのサイズがmと同じである場合、それらを2つの部分に分割すると、中央値が再び上がります。 46を削除するとします。これで2

  2. ハーフエッジデータ構造

    はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ