힙(Heap)의 삽입 연산 과정

힙의 삽입 연산

2 → 5 → 3 → 4 → 6 → 1 → 7의 순서로 최대 힙에 값을 삽입하는 과정을 살펴보자

비어있는 노드에 값을 넣고, 부모 노드와의 대소 관계를 비교하며 swap과 insert를 반복한다

 

루트 노드에 2를 삽입한다

 

5을 삽입한다. 부모 노드(2) 보다 자식 노드(5)가 크기 때문에, swap을 진행한다

 

더 이상 대소 관계를 비교할 부모 노드가 없으므로 swap을 멈춘다

 

3을 삽입한다. 부모 노드(5)와 자식 노드(3)의 대소 관계가 성립한다

 

4을 삽입한다. 부모 노드(2) 보다 자식 노드(4)가 크기 때문에, swap을 진행한다

 

swap을 진행한 후 부모 노드(5) 와 자식 노드 (4)의 대소 관계가 성립하므로 swap을 멈춘다

 

6을 삽입한다. 부모 노드(4) 보다 자식 노드(6)가 크기 때문에, swap을 진행한다

 

swap을 진행한 후 확인해보면 부모 노드(5)보다 자식 노드(6)가 크기때문에 다시 한번 swap을 진행한다

 

더 이상 대소 관계를 비교할 부모 노드가 없으므로 swap을 멈춘다

 

1을 삽입한다. 부모 노드(3)와 자식 노드(1)의 대소 관계가 성립한다

 

7을 삽입한다. 지금까지와 같은 방법으로 부모 노드와의 대소 관계를 성립시키기 위해 swap을 진행한다

이렇게 구현된 최대 힙을 배열의 형태로 정리해보자

 

배열을 사용해 힙을 구현하는 경우 첫 번째 인덱스인 0은 사용하지 않는다

루트 노드의 값(7)은 배열[1]에 넣고 왼쪽 자식 노드 값(5)은 배열[2], 오른쪽 자식 노드 값(6)은 배열[3]에 넣어준다

 

그다음 배열[2]의 왼쪽 자식 노드의 값(2)은 배열[4], 오른쪽 자식 노드의 값(4)은 배열[5]에 넣는다

 

배열[3]의 왼쪽 자식 노드의 값(1)은 배열[6], 오른쪽 자식 노드의 값(3)은 배열[7]에 넣는다

힙에서 부모 노드와 자식 노드의 인덱스는 아래와 같은 규칙을 갖는 것을 알 수 있다

→ 왼쪽 자식 노드 index = (부모 노드 index) x 2

→ 오른쪽 자식 노드 index = (부모 노드 index) x 2 + 1

→ 부모 노드 index = (자식 노드 index) / 2

→ 루트 노드의 왼쪽 자식 노드의 인덱스는 항상 2이고, 오른쪽 자식 노드의 인덱스는 항상 3이다