그림 11-4를 보면, 키 11을 키 2의 왼쪽 자식으로 만들면 완전 이진 트리를 유지할 수 있습니다. 다음으로 최대 힙의 첫 번째 특성을 만족시켜야 합니다. 키 11을 보면 부모 노드의 키 2보다 크군요. 최대 힙 특성이 깨져 있습니다. 어떻게 하면 될까요? 키 11을 부모의 키와 비교하여 크다면 서로 바꾸어 주면 됩니다. 그리고 부모의 키보다 작거나 같다면 거기에서 멈춥니다. 그럼 최대 힙 특성이 유지됩니다.

이 내용도 그림으로 살펴봅시다(그림 11-5).

▲ 그림 11-5 push 3

그림 11-5에서 키 11과 키 2를 비교합니다. 키 11이 더 크므로 두 노드의 키를 교환해 주면 되겠군요. 그림 11-6과 같이 키 11과 키 2를 교환했습니다.

▲ 그림 11-6 push 4