<aside> 🔥 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리
</aside>
<aside> 🔥 힙의 종류
8 Level 0
6 3 Level 1
2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞습니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 5 Level 2 # 자식 노드보다 크지 않아서 힙이 아닙니다..!
최소 힙 - 시간 복잡도
<aside> 🔥 삽입의 시간 복잡도
원소를 맨 밑에 넣는다 → 루트 노드까지 비교하면서 올린다.
따라서 이진 트리의 높이만큼 시간이 소요된다.
이진트리의 최대 높이는 O(log(N))
원소 추가는 O(log(N))이다.
</aside>
<aside> 🔥 추출의 시간 복잡도
추출도 삽입과 마찬가지로 트리의 높이만큼 반복된다.
따라서 추출의 시간 복잡도는 O(log(N))이다.
</aside>