[자료구조] 히프 (Heap)

히프 (Heap)

• 루트 노드가 언제나 그 트리의 최대값 혹은 최소값을 가지는 완전 이진 트리
• 최대 트리 : 노드의 키 값이 자식 노드 키 값보다 크거나 같음
• 최소 트리 : 노드의 키 값이 자식 노드 키 값보다 작거나 같음
• 힙 최초 구성 시 시간 복잡도 : O($n log {n}$)
• 우선순위 큐를 만드는데 사용!
• 트리의 최대값, 혹은 최소값을 반환하는 것이 주된 기능

​

1. 최대 히프 (Max Heap)

• 완전 이진 트리 & 최대 트리
• 부모 노드 키값 >= 자식 노드 키값
• 루트 노드 : 최대값
• 언제나 최대값이 반환됨

​

2. 최소 트리 (Min Heap)

• 완전 이진 트리 & 최소 트리
• 부모 노드 키값 <= 자식 노드 키값
• 루트 노드 : 최소값
• 언제나 최소값이 반환됨

​

​

최대 히프의 삽입 연산

1. 히프의 맨 마지막 노드에 임시로 값을 삽입
2. 부모 노드와 값을 비교 후 부모 노드보다 값이 크다면 부모 노드와 위치 바꿈
3. 반복

1) 삽입할 값 7을 맨 마지막 노드에 삽입

 

2) 부모 노드 4와 swap

 

3) 부모 노드 5와 swap (완전 이진 트리 o & 최대 트리 o) ​

 

​

최대 히프의 삭제 연산

• 최대 히프에서 삭제는 '루트 노드'만 가능
• '루트 노드' 의 값(최대값) 을 반환 이후 나머지 노드들이 '완전 이진 트리 & 최소트리'의 조건을 만족하도록 재배열

1. 루트 노드 삭제
2. 가장 마지막 노드의 값을 임시로 루트 노드로 이동
3. 왼쪽, 오른쪽 자식 노드와 비교하여서 본인이 값이 더 작다면 swap (왼쪽, 오른쪽 자식 노드 중 값이 더 큰 노드와 swap)
4. 반복

1) 루트 노드 5 삭제

 

2) 마지막 노드 2를 임시로 루트 노드에 삽입

 

3) 자식 노드 3, 4와 비교 -> 4가 3보다 더 크므로 4와 swap