heapsort alghorithm cpp

heapsort.cpp

/* #Heap Sort

###Input :
- 첫 번째 라인에는 입력할 키의 갯수(1 ≤ N ≤ 100,000)와 정수 k를 입력합니다.(1 ≤ k ≤ 30)
- 다음 라인 부터 N개의 키를 입력 합니다.
 
###Output : 
- 첫 번째 라인은 힙에서 k개의 elements 감소하는 순서로 출력 합니다.
- 두 번째 라인은 힙에서 증가하는 순서로 k 개를 출력합니다.

*/


#include <iostream>
#include <stdio.h>
 
 
void Heapify(int heap[], int size)
{
    int i, j, k=0;
    int value;
    
    for (i=size/2; i>=1; i--)
    {
        j = i;
        value = heap[i];
        while (j*2 <= size)
        {
            k = j*2;
            if (k<size)
            {
                if (heap[k] < heap[k+1]) {
                    k++;
                }
            }
            
            if (value >= heap[k]) {
                break;
            }
            else {
                heap[j] = heap[k];
                j = k;
            }
        }
        heap[j] = value;
    }
    
}
 
int getMax(int arr[], int size) {
    int ret = arr[1];
    
    arr[1] = arr[size];
    arr[size] = 0;
    
    Heapify(arr, size-1);
    return ret;
}
 
int main(void)
{
    
    
    int input, k, i;
    int in;
    
    scanf ("%d %d", &input, &k);
    
    int arr[input+1];
    
    for (i=1 ; i<=input ; i++)
    {
        scanf("%d", &arr[i]);
    }
    
    Heapify(arr, input);
    
    
    in = input;
    int le;
    for (le = 0 ; le<k ; le++) {
        printf("%d ", getMax(arr, in--));
    }
    
    printf("\n");
    int m;
    for (m = 1 ; m<=in ; m++)
    {
        printf("%d ", arr[m]);
    }
    
    printf("\n");
    return 0;
}