힙 (Heap)
- 트리 형태로 쌓인 데이터 [위키백과 내 이미지]
- 최댓값이나 최솟값을 빠르게 찾기위해 만들어진 자료구조
- 완전이진트리의 형태로, Array로 표현하기 쉬움
- 리프노드가 아닌 노드는 모두 2개의 자식을 가지며, 리프노드의 모든 데이터는 왼쪽에서 오른쪽으로 빈틈없이 채워지는 형태를 보임
- 최댓값 혹은 최솟값을 빠르게 찾기 위해서는..?
- 부모 <-> 자식 노드의 키값 사이에는 대소관계가 성립
- Max Heap (최댓값이 꼭지점에 위치)은 부모노드의 키값이 반드시 자식노드의 키값보다 큼
- 이와 반대로 Min Heap (최솟값이 꼭지점에 위치)은 부모노드의 키값이 반드시 자식노드의 키값보다 작음
- Heap의 꼭지점에 최댓값, 최솟값이 위치함으로써, 각 값들을 추적하는데 걸리는 시간복잡도는
O(1) - Heap에 요소를 추가하거나 제거하는 경우 걸리는 시간복잡도는
O(logN)
- 요소를 추가하는 경우, 이진 트리의 맨 마지막에서부터 부모 요소와 비교하면서 이동하게 됨 [아래에서 위로]
- 요소를 제거하는 경우, 이진 트리의 꼭지점에 위치한 요소를 제거, 이후 자식 요소들와 비교하면서 이동하게 됨 [위에서 아래로]
성장 += 지식