다음 그림을 봅시다.

▲ 그림 11-8 pop 1

그림 11-8에서 pop을 할 때는 무조건 루트 노드의 요소를 삭제하며 반환합니다. 루트의 인덱스는 1이므로 arr[1] 값을 따로 저장해 두었다가 반환하면 되겠군요. 문제는 그다음입니다. 루트의 키를 삭제했으니 최대 힙 특성이 깨졌습니다.

그림으로 확인해 봅시다.

▲ 그림 11-9 pop 2