C++ Huffman Tree and Pointers

Question

Estoy creando un Huffman Tree y para hacerlo empecé haciendo un Min Heap. El montón está configurado y funciona ordenando los valores por frecuencia en el documento, pero mi problema surge cuando trato de comenzar a crear el árbol.

Estoy sacando los dos elementos principales del montón y poniendo un nodo encima de ellos y reinsertándolo en el montón. El montón está basado en una matriz, por lo que no toca los punteros * izquierdo y * derecho de los nodos. Cuando el montón se reduce a un solo nodo, sin embargo, tanto los punteros de nodo izquierdo como derecho son nulos, así que creo que puede ser un problema con mis punteros ...? Soy nuevo en C++ de Java para dar mis tontos errores.

while(theHeap.getheapSize() > 1) 
    { 
     Node top; 
     Node *min1=new Node(theHeap.topandPop()); 
     Node *min2=new Node(theHeap.topandPop()); 
     top.left=min1; 
     top.right=min2; 
     top.freq=min1->freq+min2->freq; 
     theHeap.insert(top); 
    } 
    Node r=theHeap.topAndPop(); //null pointers for left and right children 

-------------------------------------- 
    //code for heap. arr is in the header file is Node *arr; 

void Heap::insert(Node c) 
{ 
    if (heapSize != arrSize) 
    { 
     heapSize=heapSize+1; 
     arr[heapSize - 1] = c; //does this call copy constructor??? 
     percolateUp(heapSize - 1); 
    } 
} 
void Heap::percolateUp(int nodeIndex) { 

    int parentIndex; 
    Node tmp; 
    if (nodeIndex != 0) 
    { 
     parentIndex = getParentPos(nodeIndex); 
     if (arr[parentIndex].freq > arr[nodeIndex].freq) 
     { 
      tmp = arr[parentIndex]; 
      arr[parentIndex] = arr[nodeIndex]; 
      arr[nodeIndex] = tmp; 
      percolateUp(parentIndex); 

     } 
    } 
} 

Answer 1

Primero, recomendaría no mezclar instancias y punteros, su tarea será mucho más simple si elige una. En este caso, creo que sería apropiado almacenar un puntero a un nodo en el montón, en lugar de una instancia, el beneficio adicional es que los punteros se comportan más como usted está acostumbrado de Java, sin necesidad de preocuparse por la construcción y asignación de copias . Solo necesita recordar eliminarlos (a diferencia de Java), algo que se puede hacer en el dtor de Heap.

En segundo lugar, para responder a la pregunta en el comentario del código: No, no se invoca el copiador en Heap :: insert(), sino que se invoca el operador de asignación. Si eso es un problema o no depende de cómo se ve tu clase Node.