문제
다음은 우선순위 큐(Priority Queue)를 최소 힙으로 구현한 것이다. 초기 상태에서 다음 연산을 순서대로 수행할 때, 세 번째 extract-min 연산에서 반환되는 값을 구하시오.
연산 순서:
- insert(8)
- insert(3)
- insert(12)
- insert(1)
- insert(7)
- insert(15)
- extract-min()
- insert(2)
- extract-min()
- insert(9)
- extract-min()
정답
3
3
해설
1~6단계 삽입 후 최소 힙의 최소값은 1이다. 7단계 extract-min()에서 1이 제거된다. 8단계에서 2를 삽입한 뒤 9단계 extract-min()에서는 2가 제거된다. 10단계에서 9를 삽입한 뒤 11단계 extract-min()에서는 남아 있는 값 중 최소인 3이 제거된다. 따라서 세 번째 extract-min의 반환값은 3이다.