fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. class heap{
  7. private:
  8.     vector<int> v;
  9.     int pred(int n){return (n-1)/2;};
  10.     int next(int n){return (v[n*2+1]>v[n*2+2])?n*2+1:n*2+2;};
  11.     int del(){
  12.         int ans=v[0];
  13.         v[0]=0;
  14.         int m=0;
  15.         int n=next(m);
  16.         while(v[m]<v[n]&&n<=v.size()){
  17.             swap(v[m],v[n]);
  18.             m=n;
  19.             n=next(m);
  20.         };
  21.         v.resize(v.size()-1);
  22.         return ans;
  23.     }
  24. public:
  25.     void add(int n){
  26.         v.push_back(n);
  27.         int m=v.size()-1;
  28.         int p=pred(m);
  29.         while((v[m]>v[p])&&(m>0)){
  30.             swap(v[m],v[p]);
  31.             m=p;
  32.             p=pred(m);
  33.         };
  34.     };
  35.     void sort(vector<int>& w){
  36.         while(v.size())w.push_back(del());
  37.     };
  38. };
  39.  
  40. int main()
  41. {
  42.     int n,m;
  43.     heap h;
  44.     cin>>n;
  45.     for(int i=0;i<n;i++){
  46.         cin>>m;
  47.         h.add(m);
  48.         };
  49.     vector<int> v;
  50.     h.sort(v);
  51.     for(int i=0;i<n;i++)cout<<v[i]<<' ';
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
5
1 3 5 2 4
stdout
copy 
5 4 3 2 1
https://ideone.com/uvYbZS
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!