최소 힙(Minimum Heap)

최소 힙(Minimum Heap)은 이진 트리 기반의 자료구조로서, 각 노드의 값이 해당 노드의 자식 노드들의 값보다 작거나 같은 특징을 가지는 완전 이진 트리이다.

최소 힙에서는 루트 노드가 항상 최소값을 가지게 된다.

최소 힙은 다음과 같은 주요한 특징을 가지고 있다:

1. 최소값 접근: 최소 힙의 루트 노드에는 항상 최소값이 위치하므로, 상수 시간(O(1)) 내에 최소값에 접근할 수 있다.
2. 최소값 삭제: 최소 힙에서 최소값을 삭제하면서 다음으로 작은 값을 새로운 루트로 설정한다. 이 때 최소 힙의 성질을 유지하기 위해 Heapify 과정을 수행하여 힙 속성을 회복한다. 최소값 삭제는 O(log N)의 시간 복잡도를 가지게 된다.
3. 원소 삽입: 새로운 원소를 최소 힙에 삽입할 때는 새로운 원소를 힙의 마지막 노드에 추가한 뒤, Heapify 과정을 수행하여 힙 속성을 회복한다. 원소 삽입은 O(log N)의 시간 복잡도를 가지게 된다.

최소 힙은 다음과 같은 응용 분야에서 유용하게 사용될 수 있다:

• 우선순위 큐: 최소 힙을 이용하여 우선순위 큐를 구현할 수 있다. 가장 우선순위가 높은 원소에 접근하거나 삭제하는 연산을 효율적으로 수행할 수 있다.
• 정렬 알고리즘: 힙 정렬(Heap Sort)은 최소 힙을 활용하여 정렬을 수행하는 알고리즘이다. 힙 정렬은 O(N log N)의 시간 복잡도를 가지며, 제자리 정렬(In-place Sorting)이 가능하다.

최소 힙은 최소값에 빠르게 접근하고, 정렬과 우선순위 큐와 같은 다양한 문제를 효율적으로 해결할 수 있는 자료구조이다.

---

최소 힙의 예시

최소 힙: [4, 7, 10, 9, 15, 12]

이 최소 힙은 다음과 같은 특징을 가지고 있다:

• 루트 노드인 4는 힙의 최소값이다.
• 루트 노드를 제외한 모든 노드에 대해 부모 노드의 값보다 작거나 같은 값을 가진다.
• 완전 이진 트리의 형태를 가지며, 레벨 순서로 노드가 배치되어 있다.

최소 힙에서의 주요 연산 예시:

1. 최소값 접근: 최소 힙에서 최소값은 항상 루트 노드에 위치하므로, 최소값에 접근하려면 힙의 루트 노드인 4에 접근하면 된다.
2. 최소값 삭제: 최소 힙에서 최소값을 삭제하면서 다음으로 작은 값을 새로운 루트로 설정한다. 최소 힙의 경우, 루트 노드인 4가 삭제되면서 7이 새로운 루트로 설정되고, Heapify 과정을 수행하여 힙 속성을 회복한다.

최소값 삭제 후 최소 힙: [7, 9, 10, 15, 12]

1. 원소 삽입: 새로운 원소를 최소 힙에 삽입할 때는 새로운 원소를 힙의 마지막 노드에 추가한 뒤, Heapify 과정을 수행하여 힙 속성을 회복한다. 예를 들어, 2를 최소 힙에 삽입하면 다음과 같이 힙 속성을 유지하면서 힙이 재조정된다.

원소 삽입 후 최소 힙: [2, 7, 10, 9, 15, 12]