그러므로 새로 추가한 원소를 루트 노드로 간주하는 서브 트리는 힙 불변성을 만족하게 됩니다. 그러나 새 원소가 여전히 새 부모 노드보다 큰 값을 가질 수 있습니다. 따라서 전체 트리에서 불변 조건이 만족하도록 교환 작업을 반복해야 합니다. 완전 이진 트리의 높이는 최대 log N이므로, 삽입 연산의 시간 복잡도는 O(log N)으로 표현할 수 있습니다. 그림 2-15와 그림 2-16은 힙의 삽입 연산 동작을 보여줍니다.

▲ 그림 2-15 힙에 새로운 원소 삽입하기(한 번 교환)

그림 2-15에서 11을 맨 마지막에 추가한 후에는 힙의 속성을 만족하지 못하게 됩니다. 그러므로 원소 10과 11을 서로 교환해야 합니다. 그림 2-16은 이러한 동작을 여러 레벨에 걸쳐서 수행하는 과정을 보여줍니다.

▲ 그림 2-16 힙에 새로운 원소 삽입하기(여러 번 교환)