fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. // Heapify for Min Heap
  6. void heapify(vector<int>& arr, int n, int i)
  7. {
  8.     int smallest = i;
  9.     int left = 2 * i + 1;
  10.     int right = 2 * i + 2;
  11.  
  12.     if (left < n && arr[left] < arr[smallest])
  13.         smallest = left;
  14.  
  15.     if (right < n && arr[right] < arr[smallest])
  16.         smallest = right;
  17.  
  18.     if (smallest != i)
  19.     {
  20.         swap(arr[i], arr[smallest]);
  21.         heapify(arr, n, smallest);
  22.     }
  23. }
  24.  
  25. // Build Min Heap
  26. void buildMinHeap(vector<int>& arr)
  27. {
  28.     int n = arr.size();
  29.  
  30.     for (int i = n / 2 - 1; i >= 0; i--)
  31.     {
  32.         heapify(arr, n, i);
  33.     }
  34. }
  35.  
  36. // Heap Sort using Min Heap (Descending Order)
  37. void heapSort(vector<int>& arr)
  38. {
  39.     int n = arr.size();
  40.  
  41.     // Step 1: Build Min Heap
  42.     buildMinHeap(arr);
  43.  
  44.     // Step 2: Move smallest to the end repeatedly
  45.     for (int i = n - 1; i > 0; i--)
  46.     {
  47.         swap(arr[0], arr[i]);
  48.         heapify(arr, i, 0);
  49.     }
  50. }
  51.  
  52. int main()
  53. {
  54.     vector<int> arr = {4, 10, 3, 5, 1};
  55.  
  56.     cout << "Original Array: ";
  57.     for (int x : arr)
  58.         cout << x << " ";
  59.  
  60.     cout << "\n";
  61.  
  62.     heapSort(arr);
  63.  
  64.     cout << "Sorted Array (Descending): ";
  65.     for (int x : arr)
  66.         cout << x << " ";
  67.  
  68.     return 0;
  69. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original Array: 4 10 3 5 1 
Sorted Array (Descending): 10 5 4 3 1
https://ideone.com/sDDxcE
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!