다음과 같은 키 값을 가지는 원소들을 공백 힙(empty heap)에 … | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 08년 1회차
다음과 같은 키 값을 가지는 원소들을 공백 힙(empty heap)에 차례대로 삽입하여 최대 힙(max heap)을 생성한 다음, 삭제 연산을 한 번 수행한 후의 결과는?4, 16, 57, 9, 32, 45, 20, 19
1
2
3
4
해설
삭제 후의 최대 힙은 레벨 순서로 45 / 32, 20 / 19, 9, 16, 4이다.
차례로 삽입하며 부모와 교환(up-heap)하면 힙 배열은 57, 32, 45, 19, 9, 16, 20, 4가 된다. 삭제는 루트 57을 꺼내고 마지막 원소 4를 루트로 올린 뒤, 더 큰 자식과 교환하며 내려간다(4↔45, 4↔20).
그 결과 배열은 45, 32, 20, 19, 9, 16, 4가 된다.
- 루트가 57이고 오른쪽 자식이 45인 트리: 마지막 원소 4만 빠진 형태로, 루트(최댓값)를 꺼내는 힙 삭제가 반영되지 않았다.
- 루트가 57이고 오른쪽 자식이 20인 트리: 최댓값 57이 아니라 45가 삭제된 형태이다.
- 20의 자식이 4, 16 순서인 트리: 4는 마지막 위치에서 내려온 원소이므로 20의 오른쪽 자식이어야 하고, 왼쪽 자식은 16이다.
오류나 개정된 내용이 보이면 알려주세요



