# 14148 - DS_2023_hw5_Sort
>author: Utin
###### tags: `Data Structure`

---

## Brief
1. Create a min heap of size ***k***.
2. If the min heap isn't full, the input number should be insert to the min heap.
3. If the min heap is full, we should replace ***min_heap[0]*** with the input integer and maintain the min heap.
4. After all, ***min_heap[0]*** will be the answer we should output.

## Solution 0

#include <iostream>

void swap(int a, int b, int* arr, int* curr);

int main() {
    int n, k;
    std::cin >> n >> k;
    int min_heap[k];
    int len = 0;

    for (int t = 0; t < n; t++) {

        int input;
        std::cin >> input;

        if (len < k) {

            // insert to the bottom
            min_heap[len++] = input;

            // maintain min heap
            int curr = len - 1;
            while (curr > 0 && min_heap[curr] < min_heap[(curr - 1) / 2])
                swap(curr, (curr - 1) / 2, min_heap, &curr);
        }

        else if (input > min_heap[0]) {

            // insert to the top
            min_heap[0] = input;

            // maintain min heap
            int curr = 0;
            while (curr * 2 + 1 < len) {
                if (curr * 2 + 2 < len) {
                    if (min_heap[curr] < min_heap[curr * 2 + 1] && min_heap[curr] < min_heap[curr * 2 + 2])
                        break;
                    if (min_heap[curr * 2 + 1] < min_heap[curr * 2 + 2])
                        swap(curr, curr * 2 + 1, min_heap, &curr);
                    else
                        swap(curr, curr * 2 + 2, min_heap, &curr);
                }
                else {
                    if (min_heap[curr] < min_heap[curr * 2 + 1])
                        break;
                    else
                        swap(curr, curr * 2 + 1, min_heap, &curr);
                }
            }

        }
    }

    // output
    std::cout << min_heap[0] << '\n';
}

void swap(int a, int b, int* arr, int* curr) {
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
    *curr = b;
}

// By Utin

## Reference