배열로 구현한 최대 힙(max heap)에 키 값 <15, 10,… | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 24년 1회차
배열로 구현한 최대 힙(max heap)에 키 값 <15, 10, 12, 8, 9, 7, 20>을 차례대로 삽입하였을 때, 값 7이 저장되어 있는 색인(index) 번호는? (단, 배열에 저장되는 키 값의 첫 번째 저장위치 색인 번호는 1이다)
1
4
2
5
3
6
4
7
해설
값 7은 색인 6에 저장된다.
최대 힙은 새 키를 마지막 위치에 넣고 부모보다 크면 위로 교환한다. 15, 10, 12, 8, 9, 7은 교환 없이 색인 1~6에 차례로 들어가므로 7은 색인 6에 놓인다.
마지막 20은 색인 7에 들어간 뒤 부모 12(색인 3), 다시 루트 15(색인 1)와 교환되어 배열은 20, 10, 15, 8, 9, 7, 12가 된다. 이 과정에서 색인 6의 7은 움직이지 않는다.
- 색인 4에는 8이 그대로 남는다.
- 색인 5에는 9가 그대로 남는다.
- 색인 7에는 20과 자리를 바꾼 12가 내려온다.
오류나 개정된 내용이 보이면 알려주세요