0

ハフマン ツリーから正しくポップするのに問題があります。現在、minheap に基づいてハフマン ツリーを作成しており、次のことを行いたいと考えています。

A と B が 2 つの異なるサブツリーであると仮定すると、A の頻度が B の頻度よりも低い場合、A が最初にポップオフされると言えます。それらが同じ頻度である場合、A の葉ノードのいずれかで ASCII 値の最小文字を見つけます。次に、A の最小の文字リーフ ノードが B のリーフ ノードよりも小さいかどうかを確認します。もしそうなら、私はBの前にAをポップオフします。そうでなければ、Bをポップオフします. <-これは私が問題を抱えていることです.

例えば：

私が入力したとしましょう： 

eeffgghh\n (every letter except for \n's frequency which is 1 is 2)

私のハフマンツリーに。次に、私のツリーは次のようになります。

        9      
       / \
    5        4    
   / \      / \
  3  h      g  f
 /\
e  \n

以下は、Huffman minheap から飛び出すための私の試みです。2つの文字の頻度が同じかどうかを比較する部分に問題があります. 誰かが助けてくれれば、それは素晴らしいことです。ありがとう！

void minHeap::heapDown(int index)
{
  HuffmanNode *t = new HuffmanNode();
  if(arr[index]->getFreq() == arr[left]->getFreq() || arr[index]->getFreq() == arr[right]->getFreq()) //arr is an array of HeapNodes
    {
      if(arr[left]->getLetter() < arr[right]->getLetter())
      {
        t = arr[index]; //equals operator is overloaded for swapping
        arr[index] = arr[left];
        arr[left] = t;
        heapDown(left);
      }
      else
      {
        t = arr[index];
        arr[index] = arr[right];
        arr[right] = t;
        heapDown(right);
      }
    }
    if(arr[index]->getFreq() > arr[left]->getFreq() || arr[index]->getFreq() > arr[right]->getFreq())
    {
      if(arr[left]->getFreq() < arr[right]->getFreq())
      {
        t = arr[index];
        arr[index] = arr[left];
        arr[left] = t;
        heapDown(left);
      }
      else
      {
        t = arr[index];
        arr[index] = arr[right];
        arr[right]  = t;
        heapDown(right);
      }//else
    }//if
}
4

1 に答える 1

1

標準 C++ ライブラリには、ヒープ アルゴリズムが含まれています。使用が許可されていない場合を除き、簡単に使用できる可能性があります。

標準 C++ ライブラリには swap(a, b) も含まれています。これは、実行している swap よりもはるかに読みやすいでしょう。ただし、heapDown でのスワッピングは非効率的です。一時的に配置する要素を保持し、要素を配置する場所が見つかるまで子をふるいにかけ、そこに配置する必要があります。

また、HuffmanNode に operator< を実装すると、コードがはるかに読みやすくなります。いずれにせよ、必要以上の比較を行っています。あなたが本当にやりたいことは（多くの詳細を省く）です：

heapDown(int index, Node* value) {
  int left = 2 * min - 1;  // (where do you do this in your code???)
  // It's not this simple because you have to check if left and right both exist
  min = *array[left] < *array[left + 1] ? left : left + 1;  // 1 comparison
  if (array[min] < to_place) {
    array[index] = array[min];
    heapDown(min, value);
  } else {
     array[index] = value;
  }

最初の比較 (3 行目) は完全に間違っています。a == b || a == c は、b==c であることを意味するものではなく、実際に b と c のどちらが小さいかについての情報も提供しません。b と c の 2 番目の比較だけを行うと、通常、間違った答えが得られます。

最後に、newすべての呼び出しで不必要に を実行していますが、決して. を実行していませんdelete。したがって、ゆっくりと、しかし容赦なくメモリをリークしています。

于 2012-12-01T05:43:08.683 に答える