Optimizing the Huffman tree algorithm from O(n^2) to O(n) with priority queue C++

I've been given this code snippet for organizing a Huffman tree.

// 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;
}

It's a pretty typical implementation (ignoring the poor templatization and obvious memory leak).

I'm supposed to revise this algorithm so that it operates O(n) instead of O(n^2) using a priority queue. I'm not exactly sure how to implement this, but I'm guessing somewhere along the lines of this:

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;
}

But it doesn't work.

For the sake of brevity, I didn't include the referenced classes, but they're implementation is pretty straight forward. I would appreciate any advice to help steer me in the right direction.