힙(Heap)

• 힙은 데이터의 최대값과 최소값을 빠르게 찾기 위해서 고안된 자료구조
• 완전 이진 트리구조를 가진다(최하단 왼쪽 노드부터 채워나가는 트리)
  

힙의 종류

• 힙은 최대값을 구하기 위한 구조와 최소값을 구하기 위한 구조로 분류
• 최대 힙(max heap): 부모 노드의 값은 자식 노드값보다 크거나 같다.
• 최소 힙(min heap): 보모 노드의 값은 자식 노드값과 같거나 작다.

힙과 이진 탐색 트리의 비교

• 공통점
  힙과 이진 탐색 트리는 모두 이진트리 자료구조를 사용한다.

• 차이점
  이진 탐색 트리의 경우
  왼쪽 자식 노드 < 부모 노드 값
  오른쪽 자식 노드 ≧ 부모 노드 값
  탐색을 위해서 사용한다.
  
  힙의 경우
  최대 힙: 자식 노드값 ≦ 부모 노드값
  최소 힙: 자식 노드값 ≧ 부모 노드값
  최대 또는 최소값을 검색하기 위해서 사용한다.

아래의 그림은 최대 힙의 구조입니다.