anekix anekix - 2 months ago 7
C++ Question

heap sort in c++ output not correct

why is this heap sort not giving correct output . the output should be a sorted array but some random output is coming. here is the link https://ideone.com/4eD289 .also can anyone review this code so that it uses modern c++ features. what are your suggestions

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

dd2 dd2
Answer

Corrections made:

  1. waste the v[0] entry for null/size of data as I would make implementation of heap easy.
  2. max_heapify() must not be called for index=0.
  3. Your for loop in heap_sort was missing parenthesis.

Corrected code for desired heap-sort you might be looking.

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