[대표 유형] 우선순위 큐

문제 설명

우선순위 큐를 이용해 수행하려는 쿼리 정보가 매개변수 queries로 주어질 때, 쿼리 수행 결과를 반환하는 solution 함수를 작성하시오.

쿼리 정보

• x (x는 자연수)
  • x를 우선순위 큐에 삽입합니다.
  • 쿼리 수행 결과에는 아무 변화가 없습니다.
• 0
  • 우선순위 큐에서 제일 작은 수를 쿼리 수행 결과에 추가하고 해당 숫자를 우선순위 큐에서 삭제합니다.
  • 만일 우선순위 큐가 비어있다면 쿼리 수행 결과에는 0을 추가합니다.

개념 설명

일반적인 큐(Queue)는 First-In-First-Out(FIFO) 구조를 따릅니다.
데일리알고 [대표 유형] 큐 참고
하지만 우선순위 큐(Priority Queue)는 큐에 삽입된 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 구조를 말합니다. 우선순위 큐에는 다음 두 가지 쿼리가 적용됩니다.

1. push X (삽입) : 우선순위 큐에 객체 X를 삽입합니다.
2. pop (삭제) : 우선순위 큐에 삽입된 객체 중 정의된 우선순위가 가장 높은 객체를 추출합니다.

우선순위 큐를 정의하기 위해서는 우선순위 큐에 삽입되는 객체와 우선순위 비교기준을 먼저 정의해야 합니다.

아래는 자연수를 원소로 가지는 우선순위 큐에 관한 예시입니다. 숫자가 작을 수록 우선순위가 높다고 가정합니다.

(push 4), (push 10), (push 7), (pop), (pop), (push 5), (pop), (push 15), (pop)

만일 우선순위 큐를 내림차순으로 정렬된 배열로 구현한다면 쿼리 동작 과정을 다음과 같이 표현할 수 있습니다.

• push(삽입) 쿼리 시, 원소를 삽입하고 우선순위가 가장 높은(=숫자가 가장 작은) 원소가 배열의 마지막에 위치할 수 있도록 내림차순으로 정렬합니다.
• pop(삭제) 쿼리 시, 배열의 마지막 원소를 추출합니다.

이러한 경우에는 push(삽입) 쿼리는 이미 정렬된 배열에서 새로운 원소를 삽입과 함께 정렬이 이루어지기 때문에 $O(N)$의 시간복잡도를 갖고 pop(삭제) 쿼리는 배열의 마지막 원소를 추출하기 때문에 $O(1)$의 시간복잡도를 갖습니다.
따라서 쿼리의 개수를 N이라 가정하면 전체 시간복잡도는 $O(N^2)$를 갖습니다.

하지만 우선순위 큐를 힙(heap)으로 구현한다면 전체 시간복잡도를 $O(NlogN)$으로 줄일 수 있습니다.

힙은 다음 두 가지 조건을 만족해야 합니다.

1. 완전 이진 트리(Complete Binary Tree) 자료구조이다.
2. 모든 노드는 자식 노드보다 우선순위가 크거나 같다.

다음 두 가지 예시는 모두 힙이 되지 않는 예시입니다. 첫 번째 예시의 경우 완전 이진 트리가 아니며, 두 번째 예시의 경우 표시된 노드가 자식 노드보다 우선순위가 작은 경우입니다.

만일 다음과 같은 힙이 있다고 가정하겠습니다.

주어진 상황에서 push 13 쿼리는 다음과 같은 순서로 동작합니다.

• 먼저, 완전 이진 트리 구조를 유지하기 위해 트리의 가장 끝에 노드 13이 추가됩니다.
• 추가된 노드가 자신의 부모 노드보다 우선순위가 높다면, 해당 노드와 부모 노드의 자리를 상호 교환(swap)합니다.
• 교환(swap) 이후에도 부모 노드보다 우선순위가 높다면, 계속 교환을 반복합니다. 최대 루트 노드까지 올라갈 수 있습니다.

pop 쿼리는 다음과 같이 동작합니다.

• 먼저, 가장 우선순위가 높은 루트 노드를 추출합니다.
• 완전 이진 트리 구조를 유지하기 위해 트리의 가장 끝에 위치한 노드를 루트 노드로 옮깁니다.
• 루트 노드가 자신의 자식 노드보다 우선순위가 낮다면, 루트 노드와 자식 노드의 자리를 상호 교환(swap)합니다.
• 교환(swap) 이후에도 자식 노드보다 우선순위가 낮다면, 계속 교환을 반복합니다. 최대 단말(리프) 노드까지 내려갈 수 있습니다.

이렇게 힙 자료구조로 우선순위 큐를 구현한 경우 우선순위 큐의 push(삽입) 쿼리와 pop(삭제) 쿼리는 $O(logN)$의 시간복잡도를 갖고 전체 시간복잡도는 $O(NlogN)$ 입니다.

제한 사항

• queries의 모든 원소는 0 이상 10,000 이하의 정수만 주어집니다.
• queries의 길이는 100,000 이하입니다.
• queries에는 0이 항상 1번 이상 포함되어 있습니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 위에서 제시된 예시와 동일합니다.

2번 테스트케이스 설명

• 아래와 같은 과정으로 쿼리가 동작합니다.

  쿼리	우선순위 큐	결과
  push 5	[5]	[]
  push 5	[5, 5]	[]
  push 5	[5, 5, 5]	[]
  pop	[5, 5]	[5]
  push 3	[5, 5, 3]	[5]
  pop	[5, 5]	[5, 3]
  pop	[5]	[5, 3, 5]

3번 테스트케이스 설명

• 아래와 같은 과정으로 쿼리가 동작합니다. 비어있는 큐에서 pop 쿼리는 0을 결과로 반환합니다.

  쿼리	우선순위 큐	결과
  pop	[]	[0]
  push 1	[1]	[0]
  pop	[]	[0, 1]
  pop	[]	[0, 1, 0]