[백준] 11279번

max heap 문제

#include <iostream>
#include <sstream>
#include <vector>

std::vector<int>numbers;

void topDown(int);
void bottomUP(int);

int main () {
    std::ostringstream buffer;
    int n;
    std::cin >> n;
    numbers.reserve(n);
    for (int i = 0; i < n; i++) {
        int _temp;
        std::cin >> _temp;
        if (!_temp && numbers.empty()) {
            // 0인 경우
            buffer << "0" <<std::endl;
            continue;
        } else if (!_temp) {
            buffer << numbers.front() <<std::endl;
            numbers.front() = numbers[numbers.size()-1];
            numbers.pop_back();
            topDown(numbers.size());
        } else {
            numbers.push_back(_temp);
            bottomUP(numbers.size());
        }
    }
    std::cout << buffer.str();
}

void topDown(int size) {
    // 2*n + 1 2(n+1)
    int current = 0;
    while (current < size) {
        int left = 2 * current + 1;
        int right = 2 * current + 2;
        int cmp = current;
        if (right < size){
            if (numbers[left] < numbers[right]) {
                cmp = right;
            } else {
                cmp = left;
            }
        } else if (left < size) {
            cmp = left;
        }
        if (numbers[current] < numbers[cmp]) {
            std::swap(numbers[current], numbers[cmp]);
        }
        if (current == cmp) {
            break;
        }
        current = cmp;
    }
}

void bottomUP(int size) {
    // parent -> (n-1)/2
    int current = size-1;
    while (current > 0) {
        int parent = (current-1) / 2;
        if (numbers[current] > numbers[parent]) {
            std::swap(numbers[current], numbers[parent]);
            current = parent;
        } else {
            break;
        }
    }
}