Heapsort implementation.

heapsort.cpp

#include <vector>
#include <iostream>
using namespace std;

int get_parent(int i){
    if( i < 1 ) return 0;
    return ( (i-1) / 2);
}

int get_left(int parent){
    return 2*parent + 1;
}

int get_right(int parent){
    return 2*parent + 2;
}

void perc_up(int current, vector<int> &x ){
    if( current == 0 ) return;
    int parent = get_parent(current);
    
    if( x[current] > x[parent] ){
        swap(x[current], x[parent]);
        perc_up(parent, x);
    }
}

void perc_down(int current, vector<int> &x, int last ){
    if( current >= last ) return;
    int left = get_left(current);
    int right = get_right(current);
    int bigger = 0;

    if( left < last && x[left] > x[current] ){
        bigger = left;
    }

    if( right < last && x[right] > x[left] ){
        bigger = right;
    }

    if( bigger ){ 
        swap(x[current], x[bigger]);
        perc_down(bigger, x, last);
    }
}

void build_heap( vector<int> & x ){
    for( size_t i = 0 ; i < x.size(); i++){
        perc_up(i, x);
    }
}

void heap_sort( vector<int> & x ){
    if( x.size() < 2 ) return;
    
    build_heap(x);
    for( size_t i = x.size()-1 ; i > 0; i-- ){
        swap( x[i], x[0] );
        perc_down(0, x, i );
    }
}

void print( vector<int> & x ) {
    for( size_t i = 0 ; i < x.size(); i++){
        cout << x[i] << " ";
    }
    cout<<endl;
}

int main(){
    int xx[] ={124,34,3,4,54,6,645,33,43};
    
    vector<int> x(begin(xx), end(xx));

    print(x);
    heap_sort(x);
    print(x);

    cin.get();
}

Used vector as underlying data structure to store the heap.