Simple Heap Sort - Hackerrank Problem Solution

Simple Heap Sort

Hackerrank Problem Solution

PROBLEM STATEMENT

Heaps can be used in sorting an array. In max-heaps, maximum element will always be at the root. Heap Sort uses this property of heap to sort the array. You are given an array of integers in any order. Sort the elements of given array in ascending order using Heap sort.

Input Format

The first line contains an integer, n , the size of the array

The second line contains n space-separated integers a[i].

Constraints

2<=n<=600 1<=a[i]<=2*10^6

Output Format

First line prints the space separated initial heap elements (having all elements) Sorted Array in new line

Sample Input 0

5
1 2 3 4 5

Sample Output 0

5 4 3 1 2 

1 2 3 4 5.

---

SOLUTION

#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> void printArray(int arr[],int n) { for(int i=0;i<n;i++) printf("%d ",arr[i]); } void heapify(int arr[], int n, int i) { int largest = i; int l = 2*i + 1; int r = 2*i + 2; if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest != i) { int temp=arr[i]; arr[i]=arr[largest]; arr[largest]=temp; heapify(arr, n, largest); } } void heapSort(int arr[],int n) { for(int i=n/2-1;i>=0;i--) heapify(arr,n,i); printArray(arr,n); for(int i=n-1;i>=0;i--) { int temp=arr[i]; arr[i]=arr[0]; arr[0]=temp; heapify(arr,i,0); } } int main() { int i,n; int arr[100]; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&arr[i]); heapSort(arr,n); printf("\n"); printArray(arr,n); /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }

Share Share Tweet Share Share Share

LIKE?

SHARE If you find this useful, please share with your friends and Community.
CODE TOGETHER..GROW TOGETHER.