Time limit: 5000ms
Memory limit: 256mb

Description:
This is an optional problem. You won't lose any mark if you skip it.

In this exercise, you are required to use heap sort program for printing K largest elements in an array. Elements in an array can be in any order. 


Sample Input 1:
5
1 2 3 4 5
3

Sample Output 1:
Input the number of integers:
Input these integers:
Input K:
K largest elements:
5 4 3


Sample Input 2:
5
9 8 7 6 5
2

Sample Output 2:
Input the number of integers:
Input these integers:
Input K:
K largest elements:
9 8


Code Template:

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    /*
        Fill in your code here...
        function to swap two elements
    */
}

void maxHeapify(int arr[], int n, int i) {
    /*
        Fill in your code here...
        complete max heapify function to maintain the heap property
    */
}

// build max heap function
void buildMaxHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, n, i);
    }
}


void printKLargest(int arr[], int n, int k) {
    buildMaxHeap(arr, n);

    /*
        Fill in your code here...
        print K largest elements in an array
    */
}

int main() {
    int k, n, *arr;
    printf("Input the number of integers:\n");
    scanf("%d",&n);
    arr = (int*)malloc(sizeof(int)*n);
    printf("Input these integers:\n");
    for(int i=0; i<n; i++)
        scanf("%d", &arr[i]);
    printf("Input K:\n");
    scanf("%d",&k);
	
    printf("K largest elements:\n");
    printKLargest(arr, n, k);

    return 0;
}