<보기>의 최대 히프를 생성할 수 있는 데이터 삽입 순서를 … | [서울시 연구사 컴퓨터공학] 20년 1회차 기출문제 상세 페이지
1[서울시 연구사 컴퓨터공학] 20년 1회차
<보기>의 최대 히프를 생성할 수 있는 데이터 삽입 순서를 바르게 나열한 것은?<보기>
1
15, 20, 35, 60, 50, 30
2
20, 30, 50, 60, 35, 15
3
30, 50, 60, 15, 35, 20
4
50, 60, 35, 15, 20, 30
해설
50, 60, 35, 15, 20, 30 순서로 삽입하면 루트 60, 둘째 층 50·35, 셋째 층 15·20·30인 그림의 최대 히프가 그대로 만들어진다.
최대 히프 삽입은 새 원소를 마지막 위치에 넣고 부모보다 크면 교환(up-heap)을 반복한다. 50 → 60 삽입 시 루트와 교환해 [60, 50] → 35는 60의 오른쪽 자식 → 15·20은 50의 자식 → 30은 35의 왼쪽 자식으로 교환 없이 자리 잡아 [60, 50, 35, 15, 20, 30] 이 된다.
- 15, 20, 35, 60, 50, 30 순서: 교환을 거치면 [60, 50, 30, 15, 35, 20] 이 되어 루트의 오른쪽 자식이 30이 된다.
- 20, 30, 50, 60, 35, 15 순서: 결과가 [60, 50, 30, 20, 35, 15] 로 오른쪽 자식이 30이고 셋째 층 배치도 다르다.
- 30, 50, 60, 15, 35, 20 순서: 결과가 [60, 35, 50, 15, 30, 20] 으로 왼쪽 자식이 35가 되어 그림과 다르다.
오류나 개정된 내용이 보이면 알려주세요
