다음 데이터들을 공백힙(empty heap)에 차례대로 삽입하여 최대힙… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 12년 1회차
다음 데이터들을 공백힙(empty heap)에 차례대로 삽입하여 최대힙(max heap)을 생성하였다. 생성된 최대힙에 삭제 연산을 두 번 수행한 후의 결과는?2, 13, 55, 8, 35, 47, 23, 19
1
2
3
4
해설
두 번 삭제한 뒤의 최대힙은 레벨 순서로 35, 19, 23, 2, 8, 13이다(루트 35, 왼쪽 자식 19의 자식 2·8, 오른쪽 자식 23의 자식 13).
차례로 삽입하며 상향 조정하면 힙 배열은 55, 35, 47, 19, 8, 13, 23, 2가 된다.
첫 삭제: 55를 빼고 마지막 원소 2를 루트로 올려 하향 조정 → 47, 35, 23, 19, 8, 13, 2.
둘째 삭제: 47을 빼고 2를 루트로 올려 더 큰 자식과 교환 → 35, 19, 23, 2, 8, 13.
- 루트 35의 왼쪽이 23, 오른쪽이 19인 트리: 첫 삭제 뒤 23은 47의 오른쪽 서브트리에 있었으므로 오른쪽 자식 자리에 남아야 한다.
- 19의 자식이 2·13이고 23의 자식이 8인 트리: 8과 13의 위치가 서로 바뀌어 하향 조정 경로와 맞지 않는다.
- 왼쪽 23(자식 2·13)·오른쪽 19(자식 8)인 트리: 좌우 서브트리와 리프 배치가 모두 실제 결과와 다르다.
오류나 개정된 내용이 보이면 알려주세요



