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

Question

I have a class built using the pimpl idiom that represents a binary max Heap and it is not working properly: the program compiles and prints the content of the array but the array is not sorted correctly. In the examples I used in the main I should see the array sorted as: 100->19->36->17->3->25->1->2->7.

I checked multiple times the correctness of the heapify algorithm and I suspect that the problem lies in the constructor.

I'm looking for help to understand what is wrong with the code.

Regarding the way the pimpl idiom has been used, it comes from the first basic example explained in the book: "Effective Modern C++" of Scott Meyers. I know there are more efficient ways to use the pimpl idiom but that is not the purpose of this 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

That can't be, because in main() function you don't even put 25 in :-)

But anyway, here:

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

If you read compilation warnings (because you compile with warnings enabled, right? :-) ) you would see:

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

which should trigger alarm bells. heapsize is of type size_t, which is unsigned. Why do you divide it by -1? -1 converted to unsigned is the max value and the result of anything unsigned divided by max unsigned will be always 0. Similarly with the comparison, no value will be bigger than the max value.

As a result, this loop does not execute even once. Iterating downward to 0 over unsigned value is a bit tricky. Some options are iterating until we reach max value:

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

or goes to "operator" (notice + 1):

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

or use signed:

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

Then the output is:

100  19  36  3  1  17  7  2

which I believe is what is expected from the numbers put in in the main().