1927번(우선순위 큐 다시풀기)

1927번 - 최소힙

최대힙과 비슷한 방식이었지만, 힙에 정수값이 들어온다는 점이 달랐다.

따라서 최대힙에서는 빈 노드가 0 이라, 어떤 노드가 추가 삭제 되도, 빈 노드에 대해서 생각할 필요가 없었다.

어차피 들어오는 값이 자연수고, 이는 0보다는 항상 크기 때문에.

하지만 최소힙에서는 비어있는 노드 값이0 이고, 이는 모든 자연수보다 작기 때문에, 비어있는 노드도 체크해줘야 했다.

이는 pop 할 때, 

왼쪽 자식 노드가 빈 경우, 오른쪽 자식 노드가 빈 경우, 둘다 빈 경우, 둘다 있는 경우를 모두 고려해서 문제를 풀었다.

(priorty_queue 를 이용하면 너무나 쉬운데.... )

<정답 코드>

#include<iostream>
 
using namespace std;
int N;
int heap[100001];
int last = 0;
void push(int n)
{
    heap[++last] = n;
 
    for (int i = last; i > 1; i /= 2)
    {
        if (heap[i] < heap[i / 2])
        {
            swap(heap[i], heap[i / 2]);
        }
        else
        {
            break;
        }
    }
 
}
void pop()
{
    printf("%d\n", heap[1]);
 
    if (last == 0)
    {
        return;
    }
 
    swap(heap[last], heap[1]);
    heap[last--] = 0;
 
    for (int i = 1; i * 2 <= last;)
    {
        if (heap[i * 2] == 0 && heap[i * 2] == 0)
        {
            break;
        }
        else
        {
            if (heap[i * 2] != 0 && heap[i * 2 + 1] == 0)
            {
                if (heap[i * 2] < heap[i])
                {
                    swap(heap[i * 2], heap[i]);
                    i = i * 2;
                }
                else
                {
                    break;
                }
            }
            else if (heap[i * 2] == 0 && heap[i * 2 + 1] != 0)
            {
                if (heap[i * 2+1] < heap[i])
                {
                    swap(heap[i * 2+1], heap[i]);
                    i = i * 2 + 1;
                }
                else
                {
                    break;
                }
            }
            else
            {
                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 * 2], heap[i]);
                        i = i * 2;
                    }
                    else
                    {
                        swap(heap[i * 2 + 1], heap[i]);
                        i = i * 2 + 1;
                    }
                }
            }
        }
    }
 
 
}
int main()
{
    cin >> N;
    while (N--)
    {
        int op;
        cin >> op;
 
        if (op == 0)
        {
            pop();
        }
        else
        {
            push(op);
        }
    }
 
    return 0;
}