[백준] 11286번

max heap을 이용해서 해결해야 하는 문제인데, 최신식으로 반영해서 했다기 보다는 보기 어지럽게 되어 있다.

O(nlogn)정도의 시간복잡도를 가질 것 이다.

#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>
#include <strings.h>

std::vector<int> arr;

void topDown();
void bottomUp(int);


int main() {
    std::ostringstream os;
    int n;
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        int _temp;
        std::cin >> _temp;
        if (arr.empty() && !_temp) {
            os << _temp << std::endl;
        } else if (!_temp) {
            os << arr.front() << std::endl;
            topDown();
        } else {
            bottomUp(_temp);
        }
    }
    std::cout << os.str();
    return 0;
}


void topDown() {
    arr.front() = arr.back();
    arr.pop_back();
    int index = 0;
    while (true) {
        int left = index*2 + 1, right = index*2 + 2;
        if (right <= arr.size()) {
            if (std::abs(arr[left]) > std::abs(arr[right]) || (std::abs(arr[left]) == std::abs(arr[right]) && arr[left] > arr[right])) {
                if (std::abs(arr[right]) < std::abs(arr[index]) || (std::abs(arr[index]) == std::abs(arr[right]) && arr[right] < arr[index])) {
                    std::swap(arr[index], arr[right]);
                    index = right;
                } else {
                    break;
                }
            } else {
                if (std::abs(arr[left]) < std::abs(arr[index]) || (std::abs(arr[left]) == std::abs(arr[index]) && arr[left] < arr[index])) {
                    std::swap(arr[index], arr[left]);
                    index = left;
                } else {
                    break;
                }
            }
        } else if (left <= arr.size()) {
            if (std::abs(arr[left]) < std::abs(arr[index]) || (std::abs(arr[left]) == std::abs(arr[index]) && arr[left] < arr[index])) {
                std::swap(arr[index], arr[left]);
                index = left;
            } else {
                break;
            }
        } else {
            break;
        }
    }
}

void bottomUp(int _temp) {
    arr.push_back(_temp);
    int index = arr.size() - 1;
    while (true) {
        int parent = (index - 1) / 2;
        if (std::abs(arr[parent]) > std::abs(arr[index])) {
            std::swap(arr[index], arr[parent]);
            index = parent;
        } else if (std::abs(arr[parent]) == std::abs(arr[index]) && arr[parent] > arr[index]) {
            std::swap(arr[index], arr[parent]);
            index = parent;
        } else {
            break;
        }
    }
}