문제 링크

no23.힙

풀이

사실 Heap 문제와 완전 동일하다... 같은 문제를 한번 더 푸는 것으로 문제풀이 시간을 단축해보고자 했다.

solution.hpp

#ifndef SOLUTION
#define SOLUTION

#include <array>
#include <cstddef>
using std::array;

enum class State { Ok, Err };

template <typename T> struct Result {
  T retval;
  State state;
};

template <typename T, class LessEq> class Heap {
public:
  constexpr static size_t MAX_N = 100'001;
  constexpr static size_t START = 1;
  constexpr static size_t parent(size_t idx) { return idx >> 1; }
  constexpr static size_t left(size_t idx) { return idx << 1; }
  constexpr static size_t right(size_t idx) { return (idx << 1) | 1; }

  explicit Heap() = default;

  auto insert(T item) noexcept -> bool {
    if (m_size >= MAX_N - 1) {
      return false;
    }

    m_size++;
    m_data[m_size] = item;

    // bubble up
    for (size_t idx = m_size;                                            //
         parent(idx) > 0 && m_less_eq(m_data[parent(idx)], m_data[idx]); //
         idx = parent(idx)) {
      std::swap(m_data[parent(idx)], m_data[idx]);
    }

    return true;
  }

  auto pop() noexcept -> bool {
    if (empty()) {
      return false;
    }

    m_data[START] = m_data[m_size];
    m_data[m_size] = T{};
    m_size--;

    for (size_t idx = START; left(idx) <= m_size;) {
      size_t child_idx = left(idx);

      if (left(idx) < m_size && // l,r 모두 확인해야함.
          m_less_eq(m_data[left(idx)], m_data[right(idx)])) {
        child_idx = right(idx);
      }

      // parent, child 확인해야함.
      if (m_less_eq(m_data[idx], m_data[child_idx])) {
        std::swap(m_data[idx], m_data[child_idx]);
      } else {
        break;
      }

      idx = child_idx;
    }

    return true;
  }

  auto peek() const noexcept -> Result<T> {
    if (empty()) {
      return Result<T>{T(), State::Err};
    }
    return Result<T>{m_data[START], State::Ok};
  }

  auto empty() const noexcept -> bool { return m_size == 0; }

private:
  array<T, MAX_N> m_data;
  size_t m_size = 0;
  LessEq m_less_eq{};
};

#endif

main.cc

#include "solution.hpp"
#include <cstdint>
#include <cstdio>
#include <ios>
#include <iostream>

struct LessEq {
  auto operator()(int a, int b) const { return a < b; }
};

int main(void) {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  freopen("sample_input-4.txt", "r", stdin);

  size_t t = 0;
  std::cin >> t;

  for (size_t tc = 1; tc <= t; ++tc) {
    Heap<int, LessEq> heap{};
    size_t n = 0;
    std::cin >> n;
    std::cout << "#" << tc << " ";

    while (n-- > 0) {

      size_t instruction = 0;
      std::cin >> instruction;

      if (instruction == 1) {
        int item;
        std::cin >> item;
        heap.insert(item);
      } else if (instruction == 2) {
        auto item = heap.peek();
        heap.pop();

        if (item.state == State::Err) {
          std::cout << "-1 ";
        } else {
          std::cout << item.retval << " ";
        }
      }
    }

    std::cout << "\n";
  }

  return 0;
}