개념
최대 힙(Max Heap)은 힙(heap) 자료구조의 일종으로, 각 노드의 값이 해당 노드의 자식들보다 크거나 같은 특성을 가지는 이진 트리입니다. 즉, 최대 힙에서는 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같습니다.
작동 방식
-
삽입(Insertion) 연산
- 최대 힙에 원소를 삽입할 때는 보통 완전 이진 트리의 마지막 위치에 원소를 추가합니다.
- 새로운 원소를 삽입한 후, 부모 노드와 비교하여 힙의 조건을 만족하도록 조정합니다. 부모 노드보다 새로운 원소가 크다면 두 노드를 교환합니다. 이 과정을 부모 노드와의 비교가 필요하지 않을 때까지 반복합니다.
- 삽입 연산은 일반적으로 O(log n)의 시간 복잡도를 가집니다.
-
삭제(Deletion) 연산
- 최대 힙에서 최댓값을 삭제할 때는 루트 노드를 제거합니다.
- 루트 노드를 제거한 후, 힙의 조건을 만족하도록 자식 노드들과 비교하여 조정합니다.
- 자식 노드들 중 더 큰 값을 가진 노드와 교환하면서 아래로 내려가며 조정합니다. 교환된 자식 노드와의 비교가 필요하지 않을 때까지 반복합니다.
- 삭제 연산은 일반적으로 O(log n)의 시간 복잡도를 가집니다.
- 최대 힙은 이러한 삽입과 삭제 연산을 통해 항상 최댓값을 루트 노드에 유지하며, O(log n)의 시간 복잡도로 최댓값을 찾을 수 있습니다.
특징
-
최대 원소: 최대 힙에서는 각 노드의 값이 해당 노드의 자식 노드들의 값보다 크거나 같습니다. 즉, 힙의 루트 노드는 전체 힙에서 가장 큰 값을 가집니다. 이러한 특성으로 인해 최대 힙은 "최댓값"을 상수 시간(O(1))에 찾을 수 있습니다.
-
완전 이진 트리: 최대 힙은 완전 이진 트리(Complete Binary Tree)의 형태를 가집니다. 이는 루트 노드부터 왼쪽에서 오른쪽으로 노드가 채워져야 하며, 마지막 레벨을 제외한 모든 레벨은 완전히 채워져야 합니다.
-
부모-자식 관계: 최대 힙에서 각 노드는 자식 노드들보다 크거나 같은 값을 가집니다. 따라서 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같습니다. 이러한 특성으로 인해 최대 힙은 최댓값을 빠르게 찾을 수 있는 자료구조로 사용됩니다.
-
삽입과 삭제: 최대 힙에 원소를 삽입할 때는 일반적으로 완전 이진 트리의 마지막 위치에 새로운 원소를 추가하고, 추가된 원소를 부모 노드와 비교하여 힙의 조건을 만족하도록 조정합니다. 원소를 삭제할 때는 루트 노드를 제거한 뒤, 힙의 조건을 만족하도록 자식 노드들과 비교하여 조정합니다. 이러한 삽입과 삭제 연산을 수행하면서도 최대 힙의 특성을 유지합니다.
최대 힙은 주로 우선순위 큐(Priority Queue)와 함께 사용되며, 최댓값을 빠르게 찾아야 하는 문제를 해결하는 데에 활용됩니다. 또한 힙 정렬(Heap Sort) 알고리즘의 핵심으로 사용되기도 합니다.
예시
다음은 최대 힙의 예시입니다:
최대 힙으로 구성된 배열: [9, 7, 6, 5, 3, 1]
해당 배열은 최대 힙의 특성을 가지고 있습니다. 최대 힙에서는 루트 노드가 가장 큰 값을 가지며, 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같습니다. 위의 배열을 힙으로 시각화하면 다음과 같습니다:
9
/ \
7 6
/ \ /
5 3 1
위 예시에서 루트 노드인 9는 전체 힙에서 가장 큰 값을 가지고 있습니다. 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같기 때문에, 모든 노드들이 최대 힙의 특성을 만족하고 있습니다.
최대 힙은 주어진 요소들을 효율적으로 저장하고, 최댓값을 빠르게 찾을 수 있도록 도와줍니다. 힙에 요소를 추가하거나 제거할 때는 힙 속성을 유지하기 위해 적절한 조치가 필요합니다.
