heap sort,I can't figure out what's wrong with my code,which doesn't output right order

Question

#include<iostream>
using namespace std;
int heapSize;
void maxHeapify(int a[],int n,int i)
{
    int l=2*i+1;
    int r=2*i+2;
    int largest=i;
    if(l<heapSize&&a[l]>a[i]) largest=l;
    if(r<heapSize&&a[r]>a[i]) largest=r;
    if(largest!=i)
    {
        swap(a[i],a[largest]);
        maxHeapify(a,n,largest);
    }
}
void heapSort(int a[],int n)
{
    heapSize=n;
    for(int i=n/2;i>=0;i--)maxHeapify(a,n,i);
    for(int i=n-1;i>=1;i--)
    {
        swap(a[0],a[i]);
        heapSize--;
        maxHeapify(a,n,0);
    }
}
int main()
{
    int a[]={1,2,3,7,9,15,13,11};
    heapSort(a,8);
    for(int i=0;i<8;i++)cout<<a[i]<<" ";
    return 0;
}

output:1 2 7 11 15 3 9 13

I want to achieve a heap sort,but something went wrong,i have tried to debug it for hours,i can't find any more bugs,maybe something wrong with the logic as well as can't figure out what's wrong with my code, which doesn't output right order.

Answer 1

In your maxHeapify fucntion you missed to compare your heap's right child with current largest. Your function will be

void maxHeapify(int a[], int n, int i) {
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int largest = i;
    if(l < heapSize && a[l] > a[i]) largest = l;
    if(r < heapSize && a[r] > a[largest]) largest = r;
    if(largest! = i)
    {
        swap(a[i], a[largest]);
        maxHeapify(a, n, largest);
    }
}