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

11279번 - 최대 힙

pop 함수와 push 함수를 구현해서 최대힙을 표현했다.

백준님 코드 중에 priority_queue 를 이용해서 엄청나게 쉽게 구현한게 있는데..

priority_queue 를 아직 사용할 줄 몰라서.. 공부를 해야겠다.

이 문제에서 배운점

- last 라는 트리에서 마지막을 나타내는 변수를 하나 지정해주니 , 처음에 엄청나게 복잡했던 코드가 엄청 간결해질 수 있었다.

- for문의 조건문을 꼭 써야한다는 편견에서 벗어나서, 요리조리 내 맘대로 표현할 수 있어야 한다는 점을 느꼈다.

?? 궁금점

pop 함수의 for문에서 

i*2 <= last 라고 할 경우에는 정답이 나오고,  i*2 + 1 <= last 라고 하면 틀렸습니다가 나온다.

for문에서의 최대값을 지정해준 건데 왜 틀린걸까...? 

==> 아하.. 그리고 i*2 자식은 있고 i*2+1 자식은 있는 경우는 완전 트리이므로 없기 떄문에!!!!

<정답 코드>

#include<iostream>
 
using namespace std;
 
int N;
int last = 0;
int heap[100001];
 
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[1], heap[last]);
    heap[last--] = 0;
 
    for (int i = 1; i*2 <= last;)
    {
        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]);
                i = i * 2;
            }
            else
            {
                swap(heap[i], heap[i * 2+1]);
                i = i * 2 + 1;
            }
        }
    }
 
 
}
 
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
 
        if (tmp == 0)
        {
            pop();
        }
        else if (tmp > 0)
        {
            push(tmp);
        }
    }
 
    return 0;
}