Envío 5404

Código

//
// Created by danie on 12/3/2021.
//


#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
#include <iostream>
#include <vector>

using namespace std;

void swap(int &a, int &b){
    a = b + a;
    b = a - b;
    a = a - b;
}

int left_child(int &i){
    return 2*(i + 1) - 1;
}

int right_child(int &i){
    return 2*(i + 1);
}

int max(int&a, int&b){
    if (a>b) return a;
    return b;
}

bool is_max_heap(vector<int> &cards){
    for(int i = (cards.size()-1)/2; i >= 0; i--){
        if( ((left_child(i) < cards.size()) && (cards[i] < cards[left_child(i)]) ) || ((right_child(i) < cards.size()) &&  (cards[i] < cards[right_child(i)]))) {
            cout<<"en el nodo "<<i<<"("<<cards[i]<<"), su hijo";
            if(right_child(i) == max(right_child(i), left_child(i))) cout<<" derecho ";
            else cout<<" izquierdo ";
            cout<<"de valor "<<cards[max(left_child(i), right_child(i))]<<" es mayor que el mismo\n";
            return false;

        }
    }
    return true;
}

void subtree_max_heapify(vector<int> &cards,int root, int &to){
    int left = left_child(root), right = right_child(root), greatest;
//    cout<<'k';
    if (right <= to && cards[right] > cards[root]) greatest = right;
    else greatest = root;
    if (left <= to && cards[left] > cards[greatest]) greatest = left;
    if (greatest != root){
        swap(cards[greatest], cards[root]);
        subtree_max_heapify(cards, greatest, to);
    }
}

void max_heapify(vector<int> &cards){
    int to = cards.size() - 1;
    for(int i = (to) / 2; i >= 0; i-- ){
        subtree_max_heapify(cards,i, to);
//        for(int card:cards) cout<<card<<' ';
//        cout<<'\n';
    }
}

void heap_sort(vector<int> &cards){
    max_heapify(cards);
    for (int i = 0; i < cards.size() - 1; i ++){
        int sub_heap_size = (((cards.size() - 1) - i));
        subtree_max_heapify(cards,0, sub_heap_size);
        swap(cards[((cards.size() - 1) - i)], cards[0]);
    }
}

//void heap_sort_test(){
////    int x = 2000, y = 7;
////    swap(x,y);
////    vector<int> cards = {0,2,5,2,67,3,5,23};
////    vector<int> cards = {9,8,7,6,5,4,3,2,1,0};
////    vector<int> cards = {0,1,2,3,4,5,6,7,8,9};
////    heap_sort(cards);
////    vector<int> cards =  {63, 8, 68, 79, 90, 72, 36, 76};
////    vector<int> cards = {3, 5, 1, 0, 1, 3, 5, 2, 1, 0, 1, 4};
//    vector<int>cards = {23, 17, 14, 6, 13, 10, 1, 5, 7, 12};
//    cout<<(is_max_heap(cards)?"true": "false")<<' ';
//    for(int card:cards) cout<<card<<' ';
//    cout<<'\n';
//}

int main(){
//void tests(){
    fast_io
    int n, in; cin>>n;
    vector<int> numbers;
    for(int i = 0; i < n; i++) {
        cin>>in;
        numbers.push_back(in);
    }
    heap_sort(numbers);
    for(int num:numbers) cout<<num<<' ';
}