그림 11-9는 최대 키를 삭제하면서 최대 힙 특성이 깨진 것을 보여 줍니다. 그렇다면 최대 힙 특성을 다시 만족시키도록 만들면 되겠군요. 먼저 최대 힙의 두 번째 특성인 완전 이진 트리를 만족시키도록 트리를 재배치해 봅시다. 힙의 마지막 요소인 키 8을 루트 노드로 만들면 완전 이진 트리를 만족하겠군요.

그림 11-10을 보면 힙의 마지막 요소를 루트 노드로 만들었습니다.

▲ 그림 11-10 pop 3

완전 이진 트리가 되었으므로 두 번째 힙 특성을 만족하게 되었습니다. 이제 최대 힙의 첫 번째 특성만 만족하면 됩니다. 그림을 보면 마지막 요소를 temp를 이용해서 가리키고 있습니다. 그런데 temp의 두 자식 노드 모두 키가 8보다 크군요. 뭔가 조치를 취해야 합니다. 이때는 자식 노드 중 키가 더 큰 노드를 선택해서 부모 노드와 바꾸어 주면 됩니다. 그 후 이런 과정을 temp가 최대 힙 특성을 만족하거나 힙의 끝에 도달할 때까지 계속합니다.