在 C++ 中使用 pimpl 构建的最大堆无法正常工作

Question

我有一个 class 使用代表二进制最大堆的 pimpl 惯用法构建的，它不能正常工作：程序编译并打印数组的内容，但数组没有正确排序。在我主要使用的示例中，我应该看到数组排序为：100->19->36->17->3->25->1->2->7.

我检查了很多次heapify算法的正确性，我怀疑问题出在构造函数上。

我正在寻求帮助以了解代码有什么问题。

关于pimpl习语的使用方式，它来自Scott Meyers的书中解释的第一个基本示例：“Effective Modern C++”。我知道有更有效的方法来使用 pimpl 习语，但这不是这个 post.

的目的

#include <vector>
#include <cstddef>

class MaxHeap{
public:
  MaxHeap();
  MaxHeap(const std::vector<int>& arr);
  ~MaxHeap();
  void maxHeapify(size_t i);
  void printHeap();

private:
  struct Impl;
  Impl* pimpl;
};

#include "binaryHeap.hpp"
#include <iostream>
using namespace std;


struct MaxHeap::Impl{
  vector<int> elements;
  size_t heapsize;
};


void MaxHeap::maxHeapify(size_t i){
    size_t size = pimpl->heapsize;
    size_t largest = i;
    size_t l = 2 * i + 1;
    size_t r = 2 * i + 2;
    if (l < size && pimpl->elements[l] > pimpl->elements[largest])
        largest = l;
    if (r < size && pimpl->elements[r] > pimpl->elements[largest])
        largest = r;
    if (largest != i)
    {
        swap(pimpl->elements[i], pimpl->elements[largest]);
        maxHeapify(largest);
    }
}

MaxHeap::MaxHeap() :pimpl(new Impl){
    pimpl->heapsize = 0;
}

MaxHeap::MaxHeap(const vector<int>& arr) :pimpl(new Impl{vector<int> (arr),arr.size()}){
    for (size_t i = (pimpl->heapsize/2)-1; i>-1; i--) {
        maxHeapify(i);
    }

}

MaxHeap::~MaxHeap(){
    delete pimpl;
    pimpl=nullptr;
}

void MaxHeap::printHeap(){
    for(size_t i=0;i<pimpl->heapsize;i++){
        cout <<pimpl->elements[i]<<"  ";
    }
}

#include <iostream>
#include "binaryHeapImpl.cpp"

using namespace std;

int main() {
    vector<int> arr;
    arr.push_back(100);
    arr.push_back(25);
    arr.push_back(1);
    arr.push_back(36);
    arr.push_back(3);
    arr.push_back(19);
    arr.push_back(17);
    arr.push_back(7);
    arr.push_back(2);
    MaxHeap testheap(arr);
    testheap.printHeap();
    return 0;
}

Answer 1

I should see the array sorted as: 10->19->36->17->3->25->1->2->7

那不可能，因为在 main() 函数中您甚至没有将 25 放入 :-)

但无论如何，这里：

for (size_t i = (pimpl->heapsize/2)/-1; i>-1; i--) {

如果您阅读编译警告（因为您在编译时启用了警告，对吧？:-)）您会看到：

warning: comparison of integer expressions of different signedness: ‘size_t’ {aka ‘long unsigned int’} and ‘int’

这应该触发警钟。 heapsize 是 size_t 类型，它是无符号的。为什么要除以-1？ -1 转换为 unsigned 是最大值，任何 unsigned 除以 max unsigned 的结果将始终为 0。与比较类似，没有值会大于最大值。

结果，这个循环连一次都没有执行。在无符号值上向下迭代到 0 有点棘手。一些选项正在迭代，直到我们达到最大值：

for (size_t i = pimpl->heapsize/2; i != (size_t)-1; i--) {

或goes to“操作员”（注意+ 1）：

for (size_t i = pimpl->heapsize/2 + 1; i-- > 0; ) {

或使用签名：

for (int i = pimpl->heapsize/2; i >= 0; i--) {

则输出为：

100  19  36  3  1  17  7  2

我相信这是 main().

中输入的数字所期望的

在 C++ 中使用 pimpl 构建的最大堆无法正常工作

Max Heap built with pimpl in c++ not working properly

c++

pimpl-idiom

binary-heap