오늘의 한줄평
^는 비트연산자이다. 제곱승을 계산하고 싶으면 pow를 써야 함^^

1927번 : 최소 힙

뭐 따로 쓸 말도 없다.

^는 비트 연산자이다

^를 제곱 연산자로 착각해서, ^를 연신 써 놓고 잘 되는 케이스만 넣어놨으니 3%에서 당연히 틀려먹지.

제곱승을 계산하려면 pow함수를 이용해야 한다 미래의 나야

문제 풀이

사실 최소 힙은 priority_queue와 결과가 같다. 따라서 그냥 queue 라이브러리 안에 있는 priority_queue에 정렬 조건을 greater로 사용하면 금방 풀리는 문제이긴 하다.

나는 힙이라는 자료구조 자체를 공부하기 위해 이 문제를 풀었으니, 구조체 형식으로 만들어보았다.

문제에서 힙 안에 들어가는 수는 $1$부터 $2^{31}-1$까지의 수라고 범위를 줬기 때문에, 최소 힙임을 고려하여 사용하지 않는 노드를 $2^{31}$로 초기화하였다.
이때, int의 범위가 $2^{31}-1$까지이기 때문에 int를 사용할 수 없었고, 0 이상의 수는 들어오지 않아 unsigned int 자료형을 사용하여 구현하였다.

delete는 키워드이므로, 함수명으로 사용할 수 없다

C++에서 delete는 할당된 메모리를 다시 운영체제로 반환하는 역할을 하는 예약어이므로, 함수명으로 사용할 수 없다.

따라서, 루트 노드를 삭제하는 함수명을 delete대신 pop으로 하였다.

최소 힙 insert 시간 복잡도

insert함수를 실행하게 되면, 가장 마지막 노드에 input값이 들어가게 되고, 최소 힙의 조건을 만족할 때 까지 부모 노드와 비교를 하며 swap하는 과정을 거친다.

부모 노드와만 비교를 하기 때문에, 최대로 비교해 봤자 트리의 높이-1번 비교를 하게 된다.

따라서, insert의 시간 복잡도는 $O(logN)$이다.

최소 힙 pop 시간 복잡도

pop함수를 실행하게 되면, 가장 마지막 노드와 루트 노드를 swap한다.
그 뒤, heap에 들어가 있는 원소의 개수를 하나 줄이고, heap의 조건을 만족하도록 새롭게 루트 노드로 올라온 친구의 자리를 조정한다.

이때, 자식 노드와 자신을 비교하여 heap 조건을 만족하는지를 찾게 되며, 최대로 비교해 봤자 트리의 높이-1번 비교를 하게 된다.

따라서, pop의 시간 복잡도는 $O(logN)$이다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

struct MinHeap // heap에 들어오는 범위가 1 ~ 2^31-1 인 경우
{
    vector<unsigned int> heap;
    int count;
    MinHeap(int n) : heap(n + 1, pow(2,31)), count(0) {}

    void insert(unsigned int input)
    {
        heap[++count] = input;

        for (int i = count; i != 1 && heap[i] < heap[i / 2]; i = i / 2)
            swap(heap[i], heap[i / 2]);
    }

    unsigned int pop()
    {
        if (count == 0)
            return 0;

        int front = heap[1];

        swap(heap[1], heap[count]);
        heap[count--] =  pow(2,31); 

        for (int i = 1; i * 2 <= count;)
        {
            if (heap[i] < heap[i * 2] && heap[i] < heap[i * 2 + 1])
            {
                break;
            }
            else if (heap[i * 2] > heap[i * 2 + 1])
            {
                swap(heap[i], heap[i * 2 + 1]);
                i = i * 2 + 1;
            }
            else
            {
                swap(heap[i], heap[i * 2]);
                i = i * 2;
            }
        }
        return front;
    }
};

int main()
{
    int N;
    scanf("%d", &N);

    MinHeap minHeap(N);

    while (N--)
    {
        unsigned int input;
        scanf("%u", &input);

        if (input == 0)
            printf("%u\n", minHeap.pop());
        else
            minHeap.insert(input);
    }
}