정의

힙(Heap)은 "부모가 자식보다 항상 크거나(최대 힙) 작은(최소 힙)" 규칙을 만족하는 완전 이진 트리입니다. 이 규칙 덕분에 루트 노드에서 항상 최대값(또는 최소값)을 즉시 확인할 수 있습니다.

핵심 특성

• ✓완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 채워져 있고, 왼쪽부터 순서대로 채워집니다.
• ✓힙 속성: 최대 힙에서는 부모 ≥ 자식, 최소 힙에서는 부모 ≤ 자식을 항상 만족합니다.
• ✓배열로 구현: 인덱스 i의 자식은 2i+1, 2i+2에, 부모는 (i-1)/2에 위치합니다.
• ✓루트 접근 O(1): 최대/최소값이 항상 루트(인덱스 0)에 있어 즉시 접근 가능합니다.

시간 복잡도