C++哈夫曼树和指针

Question

我正在创建一个哈夫曼树，为此我开始制作一个最小堆。该堆已经建立并能够按照文档中频率的排序方式进行排序，但当我尝试开始创建树时遇到了问题。

我弹出堆顶的两个项，并在它们上面放置一个节点，然后重新插入堆中。由于堆是基于数组的，所以它不会触及节点的左右指针。然而，当堆只剩下一个节点时，它的左右节点指针都为空，因此我认为这可能与我的指针有关……？我是从Java转到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);

        }
    }
}

- Westin

---

你考虑过使用 std::priority_queue 来实现堆吗？ - James McNellis

这是一个作业任务，我们不允许使用标准库。 - Westin

只是为了确保：top 超出作用域，所以希望 insert() 调用复制构造函数而不仅仅是取一个地址？ - Reinderien

我为节点编写了复制构造函数。在堆类中，我有一个节点数组，并且赋值是通过 arr[heapSize - 1] = c; 完成的，其中c是我传递作为参数的节点。 - Westin

我刚刚通过编辑我的初始问题添加了代码。 - Westin

Answer 1

首先，我建议不要混合使用实例和指针，如果您选择其中一种，您的任务会更简单。在这种情况下，我认为将节点指针存储在堆中比存储实例更合适，因为指针的行为更像您从Java熟悉的内容，无需担心复制构造和分配。您只需要记住删除它们（与Java不同），可以在Heap的dtor中完成。

其次，回答您代码注释中的问题：在Heap::insert()中不会调用复制构造函数，而是会调用赋值运算符。这是否是一个问题取决于您的Node类的具体情况。

- Andreas Magnusson