힙이란?
- 완전 이진 트리의 일종
- 여러 개의 값들 중에서 최솟값이나 최댓값을 빠르게 찾아내도록 만들어진 자료구조
- 반 정렬 상태(느슨한 정렬 상태: 항상 큰 값이 부모 노드에 있고, 작은 값이 자식 노드에 있는 정도로만 정렬되어 있다는 의미이다.)
- 중복된 값을 허용한다.
힙의 종류
- 최대 힙(max heap)
key(부모 노드) >= key(자식 노드) - 최소 힙(min heap)
key(부모 노드) <= key(자식 노드)
힙의 구현
- 힙을 저장하는 표준적인 자료 구조는 배열
- 루트 노드의 index는 항상 0이 아닌 1로 설정
- 특정 위치의 노드 번호
- 자식 노드와 부모 노드의 관계
Zoë Park