fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void heapify(vector<int>& arr, int n, int i)
  5. {
  6.     int largest = i;
  7.     int left = 2 * i + 1;
  8.     int right = 2 * i + 2;
  9.  
  10.     if(left < n && arr[left] > arr[largest])
  11.         largest = left;
  12.  
  13.     if(right < n && arr[right] > arr[largest])
  14.         largest = right;
  15.  
  16.     if(largest != i)
  17.     {
  18.         swap(arr[i], arr[largest]);
  19.         heapify(arr, n, largest);
  20.     }
  21. }
  22.  
  23. void heapSort(vector<int>& arr)
  24. {
  25.     int n = arr.size();
  26.  
  27.     // Build max heap
  28.     for(int i = n/2 - 1; i >= 0; i--)
  29.         heapify(arr, n, i);
  30.  
  31.     // Sort
  32.     for(int i = n-1; i > 0; i--)
  33.     {
  34.         swap(arr[0], arr[i]);
  35.         heapify(arr, i, 0);
  36.     }
  37. }
  38.  
  39. int main()
  40. {
  41.     vector<int> arr = {4, 10, 3, 5, 1};
  42.  
  43.     heapSort(arr);
  44.  
  45.     for(int x : arr)
  46.         cout << x << " ";
  47. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 3 4 5 10
https://ideone.com/QqCQZN
language:
C++14 (gcc 8.3)
created:
12 hours 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!