# 힙 (Heap)

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)이다.

# 최대 힙(Max Heap)

• 항상 큰 값이 부모 노드가 되고, 작은 값이 자식 노드가 되는 완전 이진 트리이다.
• 따라서 루트값은 모든 노드 값 중에 가장 크다.
• 계산 편의를 위해 인덱스는 보통 1부터 사용한다. idx → (parent: x, left: 2x, right: 2x+1)

< 힙인가? 아닌가? >

		  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  # 자식 노드보다 크지 않아서 힙이 아닙니다..!

완전 이진 트리는, 레벨이 다 채워져야 다음 레벨을 채울 수 있고, 최대 깊이 노드에 left first가 적용된다.

힙의 경우는, 왼쪽 값이 작아야 하는 BST와는 관계 없이, 부모 자식 간의 값 조건만 만족하면 된다.

위와 같은 최대 힙과 반대로 **#최소 힙(Min Heap)**도 존재하는데,

부모 노드가 작은 값, 자식 노드가 큰 값을 가지며, 루트 노드가 최저값을 가지는, 최대 힙과 뒤집힌 형태다.

• 최대 힙을 기준으로,