힙이란?
힙
-
데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전이진트리
- 완전이진트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
힙의 구조
-
최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
-
최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
-
힙에서는 가장 낮은 혹은 가장 높은 우선순위를 가지는 노드가 항상 루트 노드에 오게 되어있으며 이를 이용해 우선순위 큐와 같은 추상적 자료형 구현 가능
-
이 때 키 값의 대소 관계는 부모/자식 간에만 성립하고 형제 노드 사이에는 대소관계가 정해지지 않음
- 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다 (최대 힙의 경우, 최소 힙: 크거나 같음)
- 완전이진트리 형태를 가짐
힙과 이진탐색트리의 차이점
- 힙은 각 노드의 값이 자식 노트보다 크거나 같음(최대 힙의 경우)
- 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
- 힙은 이진탐색트리의 조건인 자식노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건이 없음
