문제
다음은 우선순위 큐(Priority Queue)를 최대 힙으로 구현한 상황이다. 초기 상태에서 insert(15), insert(8), insert(22), insert(12), insert(6), insert(18) 순으로 삽입한 후, extractMax()를 2번 수행했을 때 힙의 루트 노드 값을 쓰시오.
정답
15
15
해설
삽입 과정을 따르면 최종 힙은 [22, 12, 18, 8, 6, 15]가 된다.
- 1차 extractMax(): 22 제거 후 15를 루트로 올리고 하향 조정 → [18, 12, 15, 8, 6]
- 2차 extractMax(): 18 제거 후 6을 루트로 올리고 하향 조정 → [15, 12, 6, 8] 따라서 두 번 삭제 후 루트 노드는 15이다.