Can someone explain why this heapsort implementation doesn't work?

Question

I've spent a few hours on this, but I am new to c++ object oriented programming so probably some function argument is not passed as it should be, but I cannot find it. For this code I get the following output: 1 2 7 10 3 2 4 15

#include <iostream>

using namespace std;

class Heap {
    int * arrayX, heap_size, length;

private:
    int leftChild(int i) {
        return 2*i;
    }
    int rightChild(int i) {
        return 2*i+1;
    }
public:
    Heap(int * array, int length) {
        this->arrayX = array;
        this->length = length;
        this->heap_size = length;
    }
    void swapA(int &x,int &y)
    {
        int temp=x;
        x=y;
        y=temp;
    }
    void maxHeapify(int index) {
        int left_child = leftChild(index), right_child=rightChild(index), largest;
        if((left_child <= heap_size) && ( arrayX[left_child] > arrayX[index]))
            largest = left_child;
        else
            largest = index;
        if( (right_child <= heap_size) && (arrayX[right_child] > arrayX[index]))
            largest = right_child;
        if(largest != index) {
            swapA(arrayX[index],arrayX[largest]);
            maxHeapify(largest);
        }
    }
    void buildMaxHeap() {
        for(int i=length/2;i>0;i--)
            maxHeapify(i);
    }
    void heapsortF() {
        heap_size = length;
        buildMaxHeap();
        for(int i = heap_size; i>1; i--) {
            swapA(arrayX[1],arrayX[i]);
            heap_size--;
            maxHeapify(1);
        }

    }

    void printHeap() {
        for(int i=1; i<=length; i++)
            cout << arrayX[i] << " ";
        cout << endl;
    }
};


int main() {
    int a[]={0,4,2,3,1,10,15,2,7};
    Heap novi_heap(a, sizeof(a)/sizeof(int)-1);
    novi_heap.heapsortF();
    novi_heap.printHeap();
    return 0;
}

Answer 1

You mixed up index and largest in maxHeapify function. In second "if" expression you should compare right_child with largest, not with index, because you need to pick a vertex with maximum value out of three vertices: index, left_child and right_child.

This is a corrected line of code will look like that:

if((right_child <= heap_size) && (arrayX[right_child] > arrayX[largest]))
  largest = right_child;