c++ - 使用优先级队列 C++ 将霍夫曼树算法从 O(n^2) 优化到 O(n)

Question

我得到了这个用于组织霍夫曼树的代码片段。

// Build a Huffman tree from a collection of frequencies
template <typename E> HuffTree<E>*
buildHuff(HuffTree<E>** TreeArray, int count) {
    heap<HuffTree<E>*,minTreeComp>* forest = 
        new heap<HuffTree<E>*, minTreeComp>(TreeArray, count, count); 
    HuffTree<char> *temp1, *temp2, *temp3 = NULL;
    while (forest->size() > 1) {
        temp1 = forest->removefirst();   // Pull first two trees  
        temp2 = forest->removefirst();   //   off the list
        temp3 = new HuffTree<E>(temp1, temp2);
        forest->insert(temp3);  // Put the new tree back on list
        delete temp1;        // Must delete the remnants
        delete temp2;        //   of the trees we created
    }
    return temp3;
}

这是一个非常典型的实现(忽略糟糕的模板化和明显的内存泄漏)。

我应该修改此算法，使其使用优先级队列运行 O(n) 而不是 O(n^2)。我不确定如何实现这一点，但我猜测是这样的:

template <typename E> 
HuffTree<E>* buildHuff(HuffTree<E>** TreeArray, int count) {
    PriorityQueue<HuffTree<E>*, MIN_SORT> forest(count);
    for(int i = 0; i < count; i++) {
        forest.enqueue(TreeArray[i], TreeArray[i]->weight());
    }

    HuffTree<E> *tree = NULL;
    HuffTree<E> *left, *right = NULL;
    while(forest.size() > 0) {
        left = forest.dequeue();
        if (tree) {
            right = tree;
        }
        else {
            right = forest.dequeue();
        }
        tree = new HuffTree<E>(left, right);
        delete left;
        delete right;
    }
    return tree;
}

但它不起作用。

为了简洁起见，我没有包含引用的类，但它们的实现非常简单。如果有任何建议可以帮助我朝着正确的方向前进，我将不胜感激。

Answer 1

您的实现总是选择刚刚创建的树作为下一棵树的子树之一。那是不正确的。考虑(有序的)频率:

1, 1, 1, 1, 3

前两个节点将合并产生频率为 2 的节点，但正确的第二个节点将不包含该节点。

---

我不明白如何使用优先级队列来生成 O(n) 的解决方案，因为优先级队列需要 O(log n) 来移除最小元素。 (它可以在 O(n) 中构建，但不是按照您的方式构建。)

如果您无论如何都要使用 O(n log n) 算法，那么首先只对频率进行排序会更容易。不需要进行进一步的排序，因为生成的节点的生成频率是单调非递减的，因此不需要优先级队列来保持它们的排序。您需要的是(增量地)合并排序的叶子和(在生成时排序的)非叶子。