히프는 완전 이진 트리의 한 종류이다.

• 완전 이진 트리의 중간 레벨에는 빈 노드가 없다.

  • 따라서, 빈 노드가 구조적으로 적기 때문에 배열로 이진 트리를 구현하는 대표적인 예

• 히프는 다양한 분야에서 사용되는 자료구조이다.

  • 우선순위 큐를 구현하는 도구
  • 히프 정렬의 구현 도구

1. 히프란?

→ 이진 트리인 히프는 루트 노드가 언제나 그 트리의 최댓값 혹은 최솟값을 가진다.

• 최대 히프 : 루트 노드가 트리의 최댓값을 가지는 히프
• 최소 히프 : 루트 노드가 최솟값을 가지는 히프

최대 트리

→ 최대 히프는 기본적으로 최대 트리여야 한다.

• 최대 트리 : 각 노드의 값이 자식 노드의 값보다 크거나 같은 트리