2

ヒープ データ構造について読んでいますが、いつ max heapify 関数を使用するのか、またその理由がわかりません。

ヒープを常に max-heap に保つ挿入関数を作成しましたが、max-heapify がいつ使用されるかわかりません。

説明していただけますか？ありがとうございました

これは私のコードです:

  int  PARENT(int i) {
    return i/2;
  }

  int LEFT(int i) {
    return 2*i;
  }
  
  int RIGHT(int i ) {
    return 2*i +1;
  }

  void max_heapify(int *v, int index, int heapsize) {
    int largest;
    int left = LEFT(index);
    int right = RIGHT(index);
  
    if (left<heapsize && v[left] > v[index])
      largest = left;
    else 
      largest = index;
  
    if (right < heapsize && v[right] > v[largest])
      largest = right;
  
    if (largest !=index) {
      v[index]  = v[index] ^v[largest];
      v[largest] = v[index] ^v[largest];
      v[index] = v[index] ^v[largest];
      max_heapify(v,largest,heapsize);
    }
  }

  void insert(int *v, int * length, int value) {
    v[++*length] = value;
    int valuePos = *length;
    int parent = PARENT(valuePos);

    if (parent!=valuePos) {
      while (v[parent] < v[valuePos]) {
        v[parent] = v[parent] ^ v[valuePos];
        v[valuePos] = v[parent] ^v[valuePos];
        v[parent] = v[parent] ^ v[valuePos];
        valuePos = parent;
        parent = PARENT(valuePos);
      }
    }
  }
4

4 に答える 4

1

配列をヒープに変換するときは、heapify アルゴリズムを使用する必要があります。各配列要素を順番に新しいヒープに挿入することでそれを行うことができますが、それには O( n lg n ) の時間がかかりますが、heapify は O( n ) の時間でそれを行います。

于 2012-01-21T16:34:47.270 に答える
0

あなたmax-heapifyがそれを呼ぶように、関数は一般的なheapify関数です（ヒープはその要素をソートするために有効な比較関数を使用できます）。init配列からヒープを構築するための関数として使用することを意図しています。

ヒープを処理するための関数の複雑さ (意図された使用法を含む):

  • init( max-heapify ): O( n ) 、並べ替えられたシーケンス (配列)からヒープを初期化するために使用されます (この場合、最大並べ替え)
  • insert: O(lg n ) 、ヒープに単一の要素を挿入するために使用されます (ヒープ ツリーを「ソート済み」に維持します)
  • delete: O(lg n ) 、ヒープから「最良の」(あなたの場合は最大) 要素を削除するために使用されます (「ソートされた」ヒープ ツリーを維持します)

ただし、この質問にはタグが付けられているため、独自のヒープを実装する代わりにfromC++を使用することも検討する必要があります。考慮される操作の複雑さは、任意のヒープ実装の場合と同じであり、任意の比較関数 (事前作成またはユーザー作成) で簡単に操作できます。ヒープ実装に対するもう 1 つの利点は、それが並べ替えられたコンテナーであり、構造を破壊することなく (最初の要素だけでなく) 並べ替えられた順序ですべての要素を簡単に反復処理できることです。std::setSTL

の唯一の問題std::setは、それが一意のコンテナーであることです。つまり、同じキーを持つ要素のコピーは 1 つしか存在できません。しかし、それに対する解決策もあります -std::multiset同じキーを持つ複数のオブジェクトのソートされたインスタンスを保持します。

また、必要な使用法 (検索キーに関連付けられたデータが多い場合) によっては、std::mapまたはを試すこともできますstd::multimap。

C++独自のヒープ実装を作成する場合、最大限に使用するつもりであれば、それを別のクラス (または名前空間) に配置することを強くお勧めします。実装をそのままの形で維持するだけの場合は、質問にタグを付け直すことを検討してください。C

于 2012-01-21T17:02:32.167 に答える
0

max_heapifyヒープにするために、通常の配列で呼び出すことが期待されています。そして、配列（関数内）がすでにヒープになっているinsert必要があるメンテナンス作業を行います。v

于 2012-01-21T16:38:50.487 に答える