CS Study/CLRS (자료구조 | 알고리즘)
[CLRS] [6-1] Heaps (힙)
23학번이수현
2024. 10. 28. 21:52
1. Heaps?
- 우선 힙을 저장하는 자료구조는 배열이다.
- 일반적으로 이진 트리(Binary Tree)로 구현되는 완전 이진 트리의 형태다.
- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 구현을 쉽게 하기 위해 0인 인덱스는 사용하지 않고 1부터 사용된다.
- 그림으로 나타내면 다음과 같다. (트리의 높이는 log(n)이 된다.)
2. 힙에서의 부모노드와 자식노드의 관계
i번째 노드
- 부모 노드 인덱스 : i//2
- 왼쪽 자식 노드 인덱스 : 2*i
- 오른쪽 자식 노드 인덱스 : 2*i + 1
3. Max Heap
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
- 즉, 다음을 만족하는 Heap을 의미한다.
A[parent(i)] >= A[i]
4. Min Heap
- 부모노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
- 즉, 다음을 만족하는 Heap을 의미한다.
A[parent(i)] =< A[i]