자료 구조와 알고리즘
이진 힙을, 루트를 a[0]으로 하는 배열 a[0], a[1], a[2], …에 위쪽 단부터 차례로 왼쪽부터 채워 저장한다. a[4]의 자식과 부모로 올바른 것은?
- A자식은 a[9]와 a[10], 부모는 a[1]
- B자식은 a[8]과 a[9], 부모는 a[2]
- C자식은 a[9]와 a[10], 부모는 a[2]
정답과 해설 보기
정답: A. 자식은 a[9]와 a[10], 부모는 a[1]
루트를 a[0]으로 하는 경우, a[i]의 자식은 a[2i+1]과 a[2i+2], 부모는 a[(i−1)÷2의 버림]입니다. i = 4이면 자식은 a[9]와 a[10], 부모는 a[(4−1)÷2] = a[1]입니다. 루트를 a[1]로 하는 경우는 자식이 a[2i]와 a[2i+1], 부모가 a[i÷2]가 되므로, 어느 방식인지 확인하는 것이 중요합니다. 이처럼 힙은 완전 이진 트리이므로 포인터를 쓰지 않고 배열로 나타낼 수 있으며, 첨자 계산만으로 부모와 자식을 따라갈 수 있습니다.