fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // Function to heapify a subtree with root at given index
  5. void heapify(int arr[], int n, int i) {
  6.     int largest = i;       // Initialize largest as root
  7.     int left = 2 * i + 1;  // Left child index
  8.     int right = 2 * i + 2; // Right child index
  9.  
  10.     // If left child is larger than root
  11.     if (left < n && arr[left] > arr[largest])
  12.         largest = left;
  13.  
  14.     // If right child is larger than largest so far
  15.     if (right < n && arr[right] > arr[largest])
  16.         largest = right;
  17.  
  18.     // If largest is not root
  19.     if (largest != i) {
  20.         int temp = arr[i];
  21.         arr[i] = arr[largest];
  22.         arr[largest] = temp;
  23.  
  24.         // Recursively heapify the affected sub-tree
  25.         heapify(arr, n, largest);
  26.     }
  27. }
  28.  
  29. // Function to perform Heap Sort
  30. void heapSort(int arr[], int n) {
  31.     // Build a max heap
  32.     for (int i = n / 2 - 1; i >= 0; i--)
  33.         heapify(arr, n, i);
  34.  
  35.     // Extract elements from heap one by one
  36.     for (int i = n - 1; i > 0; i--) {
  37.         // Move current root to end
  38.         int temp = arr[0];
  39.         arr[0] = arr[i];
  40.         arr[i] = temp;
  41.  
  42.         // Call max heapify on the reduced heap
  43.         heapify(arr, i, 0);
  44.     }
  45. }
  46.  
  47. // Function to print the array
  48. void printArray(int arr[], int n) {
  49.     for (int i = 0; i < n; i++)
  50.         printf("%d ", arr[i]);
  51.     printf("\n");
  52. }
  53.  
  54. int main() {
  55.     int n;
  56.  
  57.     // Accepting user input for array size
  58.     printf("Enter the number of elements: ");
  59.     scanf("%d", &n);
  60.  
  61.     int arr[n];
  62.  
  63.     // Generating random array elements
  64.     printf("Enter %d elements: ", n);
  65.     for (int i = 0; i < n; i++) {
  66.         scanf("%d", &arr[i]);
  67.     }
  68.  
  69.     // Sorting using Heap Sort
  70.     heapSort(arr, n);
  71.  
  72.     // Printing the sorted array
  73.     printf("Sorted array: ");
  74.     printArray(arr, n);
  75.  
  76.     return 0;
  77. }
  78.  
  79.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
10
aba
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
stdout
copy 
Enter the number of elements: Enter 10 elements: Sorted array: -904549547 0 0 0 0 1 194 5433 32765 2062796998
https://ideone.com/OY7zz3
language:
C++ (gcc 8.3)
created:
213 days 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!