# 14164 - DS_2023_quiz5_Sort
>author: Utin
###### tags: `Data Structure`

---

## Brief
It is modified from ***14148 - DS_2023_hw5_Sort***

## Solution 0

#include <iostream>

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

int main() {
    int n, k;
    std::cin >> n;
    k = n / 2 + 1;
    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
    if (n % 2) std::cout << min_heap[0] << '\n';
    else if (n == 2) std::cout << (min_heap[0] + min_heap[1]) / 2 << '\n';
    else if (min_heap[1] < min_heap[2]) std::cout << (min_heap[0] + min_heap[1]) / 2 << '\n';
    else std::cout << (min_heap[0] + min_heap[2]) / 2 << '\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