Implementing HeapSort - not able to sort as per expectation

Question

I have tried a lot debugging using debugger and single stepping, but some how not able to sort the array in ascending order.

I have implemented a maxHeap and would like to sort an array in ascending order. Here is my complete code, please tell me where am I wrong.

#include <iostream>

struct maxHeap {
    int sizeOfHeap;
    int *array;
};

// Ptr to heap
maxHeap *heapPtr = new maxHeap();

//Functions
void heapSort(int *, int );
maxHeap *buildHeap(int *, int);
void heapify(maxHeap *, int);
void swap(int *, int *);

void heapSort(int *inputArray, int size) {

    heapPtr = buildHeap(inputArray,size);
        while ( heapPtr->sizeOfHeap > 0 ) {
                swap(&heapPtr->array[0],&heapPtr->array[size-1]);
                --(heapPtr->sizeOfHeap);

                                //Heapify the root
                  heapify(heapPtr,0);

        }

    }

    maxHeap *buildHeap(int *inputArray, int size) {

            heapPtr->array      = inputArray;
            heapPtr->sizeOfHeap = size;

            for(int i = (size-2)/2; i >= 0; i-- ) {
                heapify(heapPtr,i);
        }

        return heapPtr;

    }

    //Heapify procedure
    void heapify(maxHeap *theHeap, int index) {

        int root       = index;
        int leftChild  = (index << 1 ) + 1;
        int rightChild = (index << 1 ) + 2;

        if ( leftChild < theHeap->sizeOfHeap && theHeap->array[leftChild] > theHeap->array[root] )
                root = leftChild;

        if ( rightChild < theHeap->sizeOfHeap && theHeap->array[rightChild] > theHeap->array[root] )
                root = rightChild;

        if ( root != index ) {
                swap( &theHeap->array[root], &theHeap->array[index] );
                heapify(theHeap,root);

        }
    }

    void swap(int *numOne, int *numTwo) {
        int temp = *numTwo;
        *numTwo = *numOne;
        *numOne = temp;
    }



    Input - 12 11 13 5 6 7
    Expected Output - 5 6 7 11 12 13
    Output received - 13 11 7 5 6 12

Answer 1

Note that the code is in complete: it lacks a main() and the structure maxHeap, i.e., it takes unnecessary effort to even reproduce the problem. The code clearly doesn't have any debugging indication and single-stepping through the code is probably fairly pointless.

The way to find the problem is to print the content of the heap at strategic points. This way you'll see that 12 or 13 oddly stays at the top of the heap pointing at inconsistent use of the heap size. Specifically, you should change these two lines

swap(&heapPtr->array[0],&heapPtr->array[size-1]);
--(heapPtr->sizeOfHeap);

to become

swap(&heapPtr->array[0], &heapPtr->array[--(heapPtr->sizeOfHeap)];

... or, actually:

std::swap(heapPtr->array[0], heapPtr->array[--(heapPtr->sizeOfHeap)];

... but then, it is probably a homework assignment and you can't use the standard library for the actual operations. Otherwise you could have used std::priority_queue<int> or std::make_heap() and std::pop_heap().