다음과 같이 14개의 정수가 최대힙(max heap)을 표현하는 배열의… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 09년 1회차
다음과 같이 14개의 정수가 최대힙(max heap)을 표현하는 배열의 1번 위치부터 14번 위치까지 저장되어 있다. 이 배열에서 최대값을 제거하는 연산을 3번 수행한 후, 최대힙의 1번 위치부터 11번까지의 위치에 저장되어 있는 수들을 올바르게 나열한 것은? (단, 제거 연산 시 가급적 최대힙의 내용 변경을 최소화 한다고 가정한다)(데이터)
[200, 192, 63, 72, 185, 60, 62, 16, 52, 37, 22, 11, 5, 38]
1
[72, 63, 62, 60, 52, 38, 37, 22, 16, 11, 5]
2
[72, 52, 63, 38, 16, 60, 62, 37, 22, 11, 5]
3
[72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]
4
[72, 52, 63, 16, 38, 60, 62, 5, 11, 37, 22]
해설
세 차례 삭제 후 앞 11칸은 [72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]이다.
삭제는 루트를 꺼내고 마지막 원소를 루트로 올린 뒤 더 큰 자식과 교환하며 내려보내는 하향 재정렬로 진행한다.
첫 삭제(200 제거): 38이 192·185와 교환 → [192, 185, 63, 72, 38, 60, 62, 16, 52, 37, 22, 11, 5]
둘째 삭제(192 제거): 5가 185·72·52와 교환 → [185, 72, 63, 52, 38, 60, 62, 16, 5, 37, 22, 11]
셋째 삭제(185 제거): 11이 72·52·16과 교환 → [72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]
- [72, 63, 62, 60, …]처럼 내림차순으로 정렬된 나열: 힙은 부모가 자식보다 크기만 하면 되며, 삭제 연산이 전체를 정렬하지는 않는다.
- [72, 52, 63, 38, 16, …]으로 시작하는 나열: 38은 첫 삭제에서 다섯째 칸에 자리 잡은 뒤 움직이지 않고, 넷째 칸은 셋째 삭제에서 16이 채운다.
- 끝이 5, 11, 37, 22인 나열: 11은 두 자식 16과 5 중 큰 16과 교환되어 여덟째 칸에 놓이고, 5는 아홉째 칸에 그대로 남는다.
오류나 개정된 내용이 보이면 알려주세요