Heap 이란?
- 최소값 및 최대값을 최대한 빠르게 찾아내기위해 특별히 고안된 자료 구조
- 완전 이진트리(마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리의 형태)를 기본으로 하고 있음
- 일종의 반정렬(상하로만 정렬, 좌우는 정렬x) 상태를 유지한다
Heap 특징
- 트리 형태의 자료구조
- 힙의 종류에 따라 상 하의 관계만 중요, 좌 우는 중요하지 않음
- 중복을 허용한다
- 최소, 최대값 조회는 O(1) → 루트의 값을 바로 가져옴
- 삽입, 삭제는 O(logn)
Heap 종류
- Max - Heap
- Min - Heap