히프에서 삽입 연산을 하는 과정은 레스토랑에서 테이블에 앉는 과정과 비슷하다. 레스토랑에 들어서면 일단은 대기석에서 기다리면서 원하는 자리를 주문하고, 주문한 자리가 준비되었을 때 들어가 앉는다. 히프에서 삽입 연산을 하는 과정도 비슷하다. 일단은 완전 이진 트리의 형태 조건을 만족하기 위해서 현재의 마지막 노드의 다음 자리를 확장하여 자리를 만들고, 삽입할 원소를 임시로 저장한다. 그리고 나서 키값의 관계가 최대 히프가 되도록 재구성하기 위해 삽입한 원소의 키값과 현재 임시 위치에서의 부모 노드의 키값을 비교한다.

1단계 : 완전 이진 트리의 조건이 만족하도록 다음 자리를 확장한다.

2단계 : 부모 노드의 크기 조건이 만족하도록 삽입 원소의 위치를 찾는다.

예를 들어 [ 그림 7-56 ] 과 같이 노드를 여섯 개 가지고 있는 히프 노드를 삽입하는 연산을 살펴보자. (b) 와 같이 삽입 연산 1단계를 수행하여 7번 노드의 자리를 확장한다. 그런 다음 (c)와 같이 2단계를 수행하여 삽입 원소 17의 자리를 확정한다.

이번에는 17이 아니라 23을 삽입하는 과정을 살펴보자. 1단계는 같고 2단계에서 ① 삽입할 원소 23을 확장한 자리에 임시로 저장한다. ② 현재 위치에서 부모 노드 19와 키값을 비교한다. { 부모 노드의 키값 19 < 삽입 노드의 키값 23 } 이므로 히프의 크기 관계 조건을 만족하지 않는다. 이런 경우에는 자식 노드와 부모 노드의 자리를 맞바꿔 큰 키값을 부모 노드로 올린다. ③ 자리를 바꾸어 변경된 현재 위치에서의 부모 노드의 키값 20과 다시 비교한다. { 부모 노드의 키값 20 < 삽입 노드의 키값 23 } 이므로 히프의 크기 관계 조건을 만족하지 않는다. 부모 도으와 자리를 바꾼다. ④ 변경된 현재 위치에서의 부모 노드의 키값과 비교하는 작업을 해야 하는데, 현재 위치가 루트여서 더 이상 비교할 부모 노드가 없으므로 현재 위치를 삽입 원소 23의 자리로 확정한다.

히프에 삽입하는 연산은 어느 위치에서든지 부모 노드를 쉽게 찾아야 하기 때문에 순차 자료구조 방법을 사용하여 히프를 표현하고 [ 표 7-1 ] 의 배열에서의 인덱스 관계를 이용하여 부모 노드를 찾는 방법을 주로 사용한다. 1차원 배열의 순차 자료구조를 이용한 최대 히프에 원소를 삽입하는 연산을 알고리즘으로 정의하면 [ 알고리즘 7-11 ] 과 같다.

① 현재 히프의 크기를 하나 증가시켜서 노드 위치를 확장한다.

② 확장한 노드 번호가 임시 삽입 위치 i가 된다.

③ 삽입할 원소 item과 부모 노드 heap[ └i/2┘ ] 를 비교하여 부모 노드보다 작거나 같으면 임시 삽입 위치 i를 삽입 원소의 위치로 확정하고, ⑥을 수행한다.

④ 삽입할 원소 item이 부모 노드보다 크면, 부모 노드와 자식 노드의 자리를 맞바꿔 최대 히프의 관계를 만들어야 하므로 부모 노드 heap [ └i/2┘ ] 의 원소를 현재의 임시 삽입 위치 heap[i]에 저장한다.

⑤ └i/2┘ 를 임시 삽입 위치 i로 하여 ②~⑤를 반복하면서 item을 삽입할 위치를 찾는다.

⑥ 찾은 위치에 삽입할 원소 item을 저장하면 최대 히프의 재구성 작업이 완성되므로 삽입 연산을 종료한다.