Drzewo Huffmana i wskazówki Huffmana

Question

Tworzę drzewo Huffmana i do tego zacząłem od zrobienia Min Sterty. Sterta jest skonfigurowana i pracuje sortując wartości według częstotliwości w dokumencie, ale mój problem pojawia się, gdy próbuję rozpocząć tworzenie drzewa.

Pozbywam się dwóch najwyższych pozycji ze sterty i umieszczam węzeł nad nimi i ponownie umieszczam w stercie. Sterta jest oparta na tablicy, więc nie dotyka * lewego i * prawego wskaźnika węzłów. Kiedy sterta jest tylko w jednym węźle, jednak oba wskaźniki lewego i prawego węzła są puste, więc uważam, że może to być problem z moimi wskazówkami ...? Jestem nowicjuszem C++ z java, aby podać moje głupie błędy.

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

Po pierwsze nie polecam mieszania instancji i wskaźników, twoje zadanie będzie o wiele prostsze, jeśli je wybierzesz. W tym przypadku myślę, że byłoby właściwe przechowywać wskaźnik do węzła w stercie, a nie do instancji, dodatkową korzyścią jest to, że wskaźniki zachowują się bardziej, jak przyzwyczaiłeś się do Javy, nie musisz się martwić o tworzenie kopii i przypisanie jej . Trzeba tylko pamiętać, aby je usunąć (w przeciwieństwie do Javy), co można zrobić w dtor of Heap.

Po drugie, aby odpowiedzieć na pytanie w swoim komentarzu do kodu: Nie citor kopiowania nie jest wywoływany w Heap :: insert(), raczej operator przypisania jest wywoływany. To, czy jest to problem, zależy od tego, jak wygląda twoja klasa Node.