fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Heapsort
  4. //
  5. //  Created by Himanshu on 25/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. using namespace std;
  10.  
  11. void printArray (int arr[], int n) {
  12.     for (int i=0; i<n; i++) {
  13.         cout<<arr[i]<<" ";
  14.     }
  15.     cout<<endl;
  16. }
  17.  
  18. void MaxHeapify(int arr[], int i, int heapSize) {
  19.     int l, r, large;
  20.     l = 2*i + 1;
  21.     r = 2*i + 2;
  22.     if (l < heapSize && arr[l] > arr[i]) {
  23.         large = l;
  24.     } else {
  25.         large = i;
  26.     }
  27.  
  28.     if (r < heapSize && arr[r] > arr[large]) {
  29.         large = r;
  30.     }
  31.  
  32.     //Assuring heap property
  33.     if (large != i) {
  34.         swap (arr[i], arr[large]);
  35.         MaxHeapify(arr, large, heapSize);
  36.     }
  37. }
  38.  
  39. void BuildHeap(int arr[], int n) {
  40.     int k = (n/2)-1;
  41.     int j = 1;
  42.     for (int i=k; i>=0; i--) {
  43.         MaxHeapify(arr, i, n);
  44.         printf("Array after %d Max-Heapify\n", j++);
  45.         printArray(arr, n);
  46.     }
  47. }
  48.  
  49. void Heapsort (int arr[], int n) {
  50.     BuildHeap(arr, n);
  51.  
  52.     for (int i=n-1; i>=0; i--) {
  53.         swap(arr[0], arr[i]);
  54.         n--;
  55.         MaxHeapify(arr, 0, n);
  56.     }
  57. }
  58.  
  59. int main() {
  60.     int arr[] = {8, 3, 9, 2, 16, 10, 14, 7, 4};
  61.     int n = sizeof(arr)/sizeof(arr[0]);
  62.  
  63.     cout<<"Initial Array:"<<endl;
  64.     printArray(arr, n);
  65.     cout<<endl;
  66.  
  67.     Heapsort(arr, n);
  68.  
  69.     cout<<endl<<"Array after Heapsort:"<<endl;
  70.     printArray(arr, n);
  71.  
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 5344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Initial Array:
8 3 9 2 16 10 14 7 4 

Array after 1 Max-Heapify
8 3 9 7 16 10 14 2 4 
Array after 2 Max-Heapify
8 3 14 7 16 10 9 2 4 
Array after 3 Max-Heapify
8 16 14 7 3 10 9 2 4 
Array after 4 Max-Heapify
16 8 14 7 3 10 9 2 4 

Array after Heapsort:
2 3 4 7 8 9 10 14 16
https://ideone.com/6f7Rmm
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!