C++ 허프 먼 트리 및 포인터

Question

나는 허프만 트리를 만들고 있는데, 그렇게하기 위해서 나는 최소 힙을 만들기 시작했다. 힙이 설정되어 문서에서 빈도별로 값을 정렬하지만 나무를 만들기 시작할 때 문제가 발생합니다.

힙에서 상위 2 개 항목을 팝핑하고 그 위에 노드를 놓고 힙에 다시 삽입하고 있습니다. 힙은 배열 기반이므로 노드의 * 왼쪽 및 * 오른쪽 포인터를 건드리지 않습니다. 힙이 하나의 노드로 내려 갔을 때 둘 다 왼쪽 및 오른쪽 노드 포인터가 null이므로 포인터로 문제가 될 수 있다고 생각합니다 ...? 나는 자바에서 C + +에 새로운 나의 벙어리 실수를 제공합니다.

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

먼저 인스턴스와 포인터를 혼합하지 않는 것이 좋습니다. 하나를 선택하면 작업이 훨씬 간단 해집니다. 이 경우 인스턴스가 아니라 힙에 노드에 대한 포인터를 저장하는 것이 적절할 것이라고 생각합니다. 추가 이점은 포인터가 Java에서 익숙한 것처럼 동작하고 복사 생성 및 할당에 대해 걱정할 필요가 없다는 것입니다 . 힙의 dtor에서 수행 할 수있는 작업 (Java와는 달리) 만 삭제하면됩니다.

둘째, 코드 주석에 질문에 대답하십시오. 복사 연산자가 Heap :: insert()에서 호출되지 않고 할당 연산자가 호출됩니다. 그것이 문제인지 아닌지 여부는 Node 클래스의 모양에 따라 다릅니다.