힙이란?

이진 트리의 한 종류(이진 힙 - binary heap)

힙으로 불리기 위한 조건

1. 루트 노드가 언제나 최댓값 또는 최솟값을 가짐
   • 최대 힙(max heap), 최소 힙(min heap)
2. 완전 이진 트리여야 함

최대 힙(Max Heap)의 예

재귀적으로도 정의할 수 있다

• 어느 노드를 루트로 하는 서브트리도 모두 최대 힙

왼쪽, 오른쪽 서브트리보다 큰 키 값을 노드가 가지고 있고,

이 키 값은 부모 노드로 갈 수록 큰 값을 가진다는 것 이외에

왼쪽, 오른쪽 서브트리의 관계는 정의하지 않는다.

• 왼쪽과 오른쪽 서브트리의 상대적인 순서는 정해지지 않는다

이러한 구조를 느슨한 정렬 구조라고 부른다.

이진 탐색 트리와의 비교