아래의 최대힙(max heap)에서 노드를 한 개 삭제하는 연산을 실행… | [국회직 9급 컴퓨터일반] 20년 1회차 기출문제 상세 페이지

삭제 후의 최대힙은 루트가 16, 그 자식이 14와 7이고 7의 자식이 2와 3인 트리이다.
최대힙의 삭제는 최댓값인 루트에서 일어나며, 마지막 노드를 루트로 옮긴 뒤 자식 중 더 큰 값과 교환하며 내려보낸다.
루트 20을 삭제하고 마지막 노드 7을 루트로 옮긴다.
7의 자식 14, 16 중 더 큰 16과 교환한다.
7의 새 자식 2, 3은 모두 7보다 작으므로 멈춘다.
루트 20이 남고 10이 사라진 트리는 삭제가 루트가 아닌 말단에서 일어난 형태이다.
루트 20이 남고 7이 사라진 트리도 말단 노드를 지운 형태로, 최대힙의 삭제가 아니다.
루트가 14이고 오른쪽 자식이 16인 트리는 부모가 자식보다 작아 최대힙 조건을 어긴다.
루트 16의 자식이 14와 12인 트리는 힙 조건은 만족하지만, 7이 내려간 경로에 없는 12가 위치를 옮겼으므로 이 삭제 연산의 결과가 아니다.