Huffman Tree Creation C++

Question

I have a class Node which has Node *left and Node *right as the variables. Now I have a function to build the huffman tree as follows

int x = pQueue.size();

for(int i=0;i<x-1;i++){

    Node *z = new Node;
    z->left = &pQueue.extractMin();
    z->right = &pQueue.extractMin();
    z->setchar(NULL);
    z->setfrequency(z->left->getFrequency() + z->right->getFrequency());
    pQueue.insert(z);

}

This is the standard function to create huffman tree. However the problem is this. Initially when a new Node* z is created and its left and right child are assigned, during the next execution of the loop the left and right child of z are re assigned, and I am losing the initially assigned values. I was under the impression that during each execution of the loop, new object is created and its left and right child will have different memory locations. But this is not happening. How do I make a new object each time the loop is executed.??

Here is what I am getting

If you check the node with frequency 14 is assigned some memory locations in the first execution as its left and right children . however in the next execution the left and right child of frequency 14 node is null and children of frequency 25 node are set to the previous locations. i expect them to be the same assigned during first round for frequency 14 node and new locations for frequency 25 node.

Answer 1

If, as you said, pQueue is a vector of Node objects (and I'm assuming std::vector - if not, ignore the answer!), by using vector::insert(), you are actually adding an iterator rather than a Node object. Try something like this instead:

int x = pQueue.size();

for(int i=0;i<x-1;i++){

    Node z;
    z.left = &pQueue.extractMin();
    z.right = &pQueue.extractMin();
    z.setchar(NULL);
    z.setfrequency(z.left->getFrequency() + z.right->getFrequency());
    pQueue.push_back(z);
}