heap sort in C++ output not correct

Question

Почему эта сортировка кучи не дает правильного вывода. выход должен быть отсортированным массивом, но какой-то случайный выход идет. вот ссылка https://ideone.com/4eD289. Также можно просмотреть этот код, чтобы он использовал современные возможности C++. каковы ваши предложения

#include<iostream> 
    #include<algorithm> 
    #include<vector> 

int max_heapify(std::vector<int>& v, int i){ 

    int l = 2*i; 
    int r = 2*i + 1; 
    int largest = 0; 

    if((l < v.size()) && (v[l] > v[i])){ 

     largest = l; 
    } 
    else{ 
     largest = i; 
    } 

    if ((r<v.size()) && (v[r] > v[largest])){ 
     largest = r; 
    } 
    if (largest != i){ 

     std::swap(v[i], v[largest]); 
     max_heapify(v, largest); 
    } 

    return 0; 
} 


int build_max_heap(std::vector<int> &v){ 

    for(int i = v.size()/2; i >= 0; i--){ 
     max_heapify(v, i); 

    } 
    return 0; 

} 

int heap_sort(std::vector<int>& v){ 
    build_max_heap(v); 
    int length = v.size(); 
    for(int i = length-1 ; i>=1; i--) 
    std::swap(v[0], v[i]); 
    length--; 
    max_heapify(v, v[length]); 

} 

int main(){ 
std::vector<int> v = { 1, 2, 9, 8, 3, 4, 7, 6, 5}; 
heap_sort(v); 

for(auto& e : v) std::cout<<e<<" "; 

return 0; 
} 

Answer 1

Исправления, сделанные:

1. с отходами V [0] для входа в нуле/размера данных, как я хотел бы сделать реализацию кучи легкого.
2. max_heapify() не следует вызывать для индекса = 0.
3. В вашей петле цикла в heap_sort отсутствовала скобка.

Исправленный код для желаемой сортировки кучи, которую вы, возможно, ищете.

#include<iostream> 
#include<algorithm> 
#include<vector> 

int max_heapify(std::vector<int>& v, int i,int len){ 

    int l = 2*i; 
    int r = 2*i + 1; 
    int largest = 0; 

    if((l < len) && (v[l] > v[i])){ 

     largest = l; 
    } 
    else{ 
     largest = i; 
    } 

    if ((r<len) && (v[r] > v[largest])){ 
     largest = r; 
    } 
    if (largest != i){ 

     std::swap(v[i], v[largest]); 
     max_heapify(v, largest,len); 
    } 

    return 0; 
} 


int build_max_heap(std::vector<int> &v){ 

    for(int i = v.size()/2; i > 0; i--){ 
     max_heapify(v, i,v.size()); 

    } 
    return 0; 

} 

int heap_sort(std::vector<int>& v){ 
    build_max_heap(v); 
    int length = v.size(); 
    for(int i = length-1 ; i>=1; i--){ 
     std::swap(v[1], v[i]); 
     length--; 
     max_heapify(v, 1,i); 
    } 

} 

int main(){ 
std::vector<int> v = { 0 \* NULL entry *\ , 1, 2, 9, 8, 3, 4, 7, 6, 5}; 
heap_sort(v); 

for(auto& e : v) std::cout<<e<<" "; 

return 0; 
}