배열(array)로 표현한 이진 트리 중에서 최소 힙(minimum h… | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 23년 1회차
배열(array)로 표현한 이진 트리 중에서 최소 힙(minimum heap)에 해당하지 않는 것은?
1
1 3 13 7 9 10 20 17 25
2
1 3 13 9 7 20 17 25 10
3
1 3 17 7 13 25 20 9 10
4
1 9 3 17 10 13 7 20 25
해설
최소 힙이 아닌 것은 1 3 13 7 9 10 20 17 25이다.
배열을 인덱스 1부터 채우면 인덱스 i의 자식은 , 이고, 최소 힙은 모든 부모 ≤ 자식이어야 한다. 위 배열에서 인덱스 3의 13은 자식(인덱스 6, 7)이 10, 20인데 10 < 13이므로 힙 조건을 어긴다.
- 1 3 13 9 7 20 17 25 10: 3의 자식 9·7, 13의 자식 20·17, 9의 자식 25·10 모두 부모보다 크다.
- 1 3 17 7 13 25 20 9 10: 3의 자식 7·13, 17의 자식 25·20, 7의 자식 9·10 모두 조건을 만족한다.
- 1 9 3 17 10 13 7 20 25: 9의 자식 17·10, 3의 자식 13·7, 17의 자식 20·25 모두 조건을 만족한다.
오류나 개정된 내용이 보이면 알려주세요