0

我在从霍夫曼树中正确弹出时遇到问题。现在我正在创建一个基于 minheap 的 Huffman 树,我想做以下事情:

如果我们假设 A 和 B 是两个不同的子树,我会说如果 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 中弹出的尝试。我在比较两个字母的频率是否相同时遇到了麻烦。如果有人可以提供帮助,那就太好了。谢谢!

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),它比您正在执行的交换更具可读性。但是,在 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;
  }

您的第一个比较(第三行)是完全错误的。a == b || a == c 并不意味着 b==c,或者确实为您提供任何关于 b 和 c 中哪个较小的信息。只对 b 和 c 进行第二次比较通常会给你错误的答案。

最后,您new在每次调用时都做了不必要的操作,但从不做delete. 因此,您正在缓慢但无情地泄漏内存。

于 2012-12-01T05:43:08.683 回答