루트 노드의 인덱스를 1로 하는 1차원 배열을 이용하여 최대 힙(max… | [7급 국가직 자료구조론] 22년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 22년 1회차
루트 노드의 인덱스를 1로 하는 1차원 배열을 이용하여 최대 힙(max heap)을 구현한 후, 다음 데이터를 차례대로 하나씩 힙에 삽입하였다. 이후 힙 삭제 연산을 1회 수행한 후 배열의 인덱스 6에 저장된 데이터는?15, 8, 10, 18, 22, 13, 26, 7
1
8
2
10
3
13
4
15
해설
삭제 후 인덱스 6에 저장된 데이터는 10이다.
삽입 과정에서 18은 8·15와, 22는 15·18과, 13은 10과, 26은 13·22와 교환되며 올라가 힙은 [26, 18, 22, 8, 15, 10, 13, 7]이 된다.
삭제 시 루트 26을 빼고 마지막 7을 루트로 옮긴 뒤 더 큰 자식과 교환한다: 7↔22, 이어 7↔13. 결과는 [22, 18, 13, 8, 15, 10, 7]이고 인덱스 6은 10 그대로이다.
- 8: 인덱스 4에 있다.
- 13: 재배치로 인덱스 3으로 올라간다.
- 15: 인덱스 5에 있다.
오류나 개정된 내용이 보이면 알려주세요