What is a Heap?

힙(heap)은 하나의 단순한 불변성(invariant)을 따르는 트리 모양의 데이터 구조입니다. 즉, 모든 부모는 자식보다 작거나 같습니다. 가장 작은 값은 항상 루트에 위치하며, O(1)의 시간 복잡도로 읽을 수 있습니다. 이러한 특성을 가진 것을 최소 힙(min-heap)이라고 하며, 가장 큰 값이 루트에 위치하는 반대 형태를 최대 힙(max-heap)이라고 합니다.

핵심적인 부분은 저장 방식입니다. 트리 구조로 생각하지만, 힙은 평면적인 배열(array)에 저장됩니다. 인덱스 i에 있는 노드의 경우:

• 부모는 인덱스 (i - 1) / 2에 위치합니다.
• 왼쪽 자식은 인덱스 2 * i + 1에 위치합니다.
• 오른쪽 자식은 인덱스 2 * i + 2에 위치합니다.

포인터나 노드 객체 없이 오직 인덱스 산술만 사용합니다. 덕분에 힙은 캐시 친화적이며 구현하기 쉽습니다.

최소 힙의 다섯 가지 주요 연산은 다음과 같습니다:

1. Peek: 가장 작은 값(루트)을 반환합니다.
2. Insert: 값을 추가하고 제자리를 찾을 때까지 위로 올립니다(bubble up).
3. ExtractMin: 가장 작은 값을 제거하고 반환합니다.
4. Size: 저장된 값의 개수를 반환합니다.
5. IsEmpty: 힙이 비어 있는지 확인합니다.

이제 MinHeap 클래스를 만들어 봅시다!