sorte tas, je ne peux pas comprendre ce qui ne va pas avec mon code, qui ne commande droit sortie

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; 
} 

sortie: 1 2 7 11 15 3 9 13

Je veux obtenir une sorte de tas, mais quelque chose a mal tourné, j'ai essayé de le déboguer pendant des heures, je ne trouve plus de bugs, peut-être quelque chose qui ne va pas avec la logique et je n'arrive pas à comprendre ce qui ne va pas avec mon code .

Answer 1

Dans votre fonction maxHeapify, vous avez manqué de comparer le bon enfant du tas avec le plus grand courant. Votre fonction sera

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); 
    } 
}