[자료구조] 힙 삽입

 

우선순위 큐 구현에서 힙 자료구조의 시간복잡도가 O(log N)이므로, 힙으로 우선순위 큐를 구현해야 한다고 배웠다.

 

배열, 연결리스트에 삽입, 삭제, 탐색, 순회가 있듯 힙에도 삽입 기능이 있다. 

 

힙 삽입

• 힙에 데이터를 추가하는 것 
• O(log N) 
• 최소 힙(min heap) 삽입, 최대 힙(max heap) 삽입이 있다. 

 

최소 힙(min heap) 삽입

1. 그래프가 최소 힙인지 아닌지 확인
   1. 완전 이진 트리인지 확인
   2. 각 노드의 값이 자식 노드의 값보다 작거나 같은지 확인
2. 힙에 원소 삽입 (완전 이진 트리를 만족하도록 삽입)
   1. 부모노드와 비교해서 최소 힙 조건을 만족하는지 확인
   2. 최소 힙 조건을 만족하지 않으면 부모 노드와 스왑 

 

우선 위 그래프가 최소 힙인지 아닌지 확인해야 한다. 

최소 힙은 다음 조건을 만족해야 한다. 

• 완전 이진 트리
• 각 노드의 값은 자식 노드의 값보다 작거나 같아야 한다. 

각 노드는 자식 노드를 0 ~ 2개를 가지고, 3층 노드들은 왼쪽 노드부터 채워져 있으므로, 완전 이진 트리가 맞다. 

각 노드의 값은 자식 노드의 값보다 작은 값을 가지므로, 최소 힙이 맞다. 

 

 

최소 힙이 맞으므로, 이제 삽입을 할 수 있다. 

 

5를 삽입해보자. 

 

완전 이진 트리를 만족해야 하므로, 5는 9의 왼쪽 자식 노드로 들어간다. 

 

최소힙은 노드의 값이 자식 노드의 값보다 작거나 같아야 한다. 

9는 5보다 크므로, 최소힙 조건을 만족하지 않는다. 

따라서 둘의 위치를 바꿔야 한다. 

 

 

3은 5보다 작으므로, 최소힙 조건을 만족한다. 

최소 힙 삽입이 끝났다. 

 

 

최대 힙(max heap) 삽입 

1. 그래프가 최대 힙인지 아닌지 확인
   1. 완전 이진 트리인지 확인
   2. 각 노드의 값이 자식 노드의 값보다 크거나 같은지 확인
2. 힙에 원소 삽입 (완전 이진 트리를 만족하도록 삽입)
   1. 부모노드와 비교해서 최대 힙 조건을 만족하는지 확인
   2. 최대 힙 조건을 만족하지 않으면 부모 노드와 스왑 

 

위 그래프가 최대 힙인지 아닌지 확인해야 한다. 

최대 힙은 다음 조건을 만족해야 한다. 

• 완전 이진 트리
• 각 노드의 값은 자식 노드의 값보다 크거나 같아야 한다. 

각 노드는 자식 노드를 0 ~ 2개를 가지고, 3층 노드들은 왼쪽 노드부터 채워져 있으므로, 완전 이진 트리가 맞다. 

각 노드의 값은 자식 노드의 값보다 큰 값을 가지므로, 최대 힙이 맞다. 

 

15를 삽입해보자. 

 

 

완전 이진 트리를 만족해야 하므로, 15는 5의 오른쪽 자식 노드로 들어간다. 

 

최대 힙은 노드의 값이 자식 노드의 값보다 크거나 같아야 한다. 

5는 15보다 작으므로, 최대힙 조건을 만족하지 않는다.

따라서 둘의 위치를 바꿔야 한다. 

 

 

10은 15보다 작으므로, 최대 힙 조건을 만족하지 않는다. 

둘의 위치를 바꿔야 한다. 

 

 

최대 힙의 삽입이 끝났다.