0

最大ヒープを保持する配列表現があります。「d」、「b」、「c」の配列の場合、b、c、d であるはずですが、b、d、c を保持しています。これは私の追加方法です：

public boolean add (E e) {
  ensureCapacity(objectCount + 1);
  pq[objectCount++] = e;

  //percolate up
  for (int i = objectCount - 1; i >= 0; i--) {
     if (priorityComparator.compare(pq[i], pq[parent(i)]) >= 0) {
          E tmp = pq[parent(i)];
          pq[parent(i)] = pq[i];
          pq[i] = tmp;

     }
  }

  modCount++;

  return true;
  }

次に「a」を追加すると、a、b、c、d に正常に変更されます。メソッドを修正して、左の子 (2*i+1) と右の子 (2*i+2) をチェックし、優先度の高いキュー (a は b よりも優先度が高く、等）？

4

1 に答える 1

1

MAXヒープではなくMINヒープがあると思います。

私はあなたのコードを見ていませんが：

最小ヒープは、次のことを保証します。

  1. ルートは常に最小です（あなたの場合は要素0）
  2. ツリーは常に左から順に並べられます (これはどのヒープにも当てはまります)

あなたの場合、出力 b、d、c は完全に正当です。b を削除して、heapify を再度呼び出すと、出力は c、d になります。

Wiki リンク: http://en.wikipedia.org/wiki/Binary_heap

編集: あなたの場合、「a」に「b」よりも高い優先度を与えることを検討している場合、はい、MAX ヒープがあります。

于 2012-11-08T04:52:53.273 に答える