대칭 최소-최대 힙(SMMH)이란?
대칭 최소-최대 힙(Symmetric Min-Max Heap, SMMH)은 루트를 제외한 모든 노드가 정확히 하나의 원소를 갖는 완전 이진 트리(complete binary tree)로 정의되는 자료구조입니다. 루트 노드는 항상 비어 있으며, 전체 노드 수는 m + 1개입니다. 여기서 m은 힙에 저장된 원소의 개수입니다.
SMMH는 하나의 트리 안에서 최솟값과 최댓값을 동시에 효율적으로 관리할 수 있도록 설계된 양방향 우선순위 큐(double-ended priority queue)용 자료구조입니다.
SMMH의 핵심 성질
SMMH의 임의의 노드를 y, 그리고 y를 루트로 하는 서브트리에 속한 원소들 중 y 자신의 원소(있는 경우)를 제외한 집합을 elements(y)라고 합시다. elements(y)가 공집합이 아닐 때, 모든 노드 y는 다음 두 가지 성질을 만족해야 합니다.
- y의 왼쪽 자식은 elements(y)의 최솟값을 가진다.
- y의 오른쪽 자식(존재하는 경우)은 elements(y)의 최댓값을 가진다.
예시로 확인하기
그림 1은 12개의 원소를 가진 SMMH의 예입니다. 값 81을 가진 노드를 y라고 하면, elements(y) = {6, 7, 15, 31, 41}이 됩니다. 이때 y의 왼쪽 자식은 이 집합의 최솟값인 6을, 오른쪽 자식은 최댓값인 41을 담고 있습니다. 실제로 이 트리의 모든 노드가 앞서 설명한 두 성질을 만족함을 검증할 수 있습니다.
배열 기반 구현과 상수 시간 조회
SMMH는 완전 이진 트리이므로, 완전 이진 트리를 배열에 매핑하는 표준 방식을 적용한 암시적 자료구조(implicit data structure) 형태로 저장합니다. 포인터 없이 배열 인덱스만으로 부모·자식 관계를 계산할 수 있어 메모리 효율성이 뛰어나다는 장점이 있습니다.
- m = 1인 경우: 최솟값과 최댓값이 같은 원소이며, 루트의 왼쪽 자식에 위치합니다.
- m > 1인 경우: 최솟값은 루트의 왼쪽 자식에, 최댓값은 루트의 오른쪽 자식에 위치합니다.
따라서 getMin과 getMax 연산은 O(1) 시간에 수행됩니다.
SMMH의 필요충분조건: A1 ~ A3
루트가 비어 있고 나머지 모든 노드에 원소가 하나씩 있는 (m + 1)노드 완전 이진 트리가 SMMH이기 위한 필요충분조건은 다음 세 가지입니다.
- A1. 오른쪽 형제(right sibling)를 가진 모든 노드 y에 대해, y의 원소는 y의 오른쪽 형제의 원소보다 작거나 같다.
- A2. 조부모(grandparent)를 가진 모든 노드 y에 대해, 조부모의 왼쪽 자식의 원소는 y의 원소보다 작거나 같다.
- A3. 조부모를 가진 모든 노드 y에 대해, 조부모의 오른쪽 자식의 원소는 y의 원소보다 크거나 같다.
여기서 주목할 점은, 노드 y에서 성질 A1이 이미 만족되어 있다면 A2와 A3 중 최대 하나만 위반될 수 있다는 사실입니다. 이 특성 덕분에 삽입·삭제 과정에서 깨진 조건을 한 번의 교환으로 복원할 수 있습니다.
삽입·삭제 알고리즘과 시간 복잡도
성질 A1부터 A3를 유지하도록 구현하면 매우 단순한 형태의 삽입·삭제 알고리즘을 얻을 수 있습니다. 이 알고리즘들은 최소 힙(min heap)과 최대 힙(max heap)의 대응 알고리즘을 변형한 것으로, 시간 복잡도는 O(log m)입니다.
삽입 연산 예시: 원소 3 삽입하기
그림 1의 SMMH에 3을 삽입하는 과정을 살펴보겠습니다. SMMH는 완전 이진 트리이므로, 새 노드는 반드시 마지막 위치, 즉 그림 2에 표시된 자리에 추가해야 합니다. 이 새 노드를 B라고 부르겠습니다.
예제에서 B는 빈 노드(empty node)를 나타내며, 원소 3이 이 자리에 삽입됩니다. 삽입 후에는 A1~A3 조건이 깨졌는지 검사하고, 위반이 발견되면 형제 노드 또는 조부모의 자식 노드와 원소를 교환하는 sift-up 과정을 통해 힙의 성질을 복원합니다. 이 과정은 트리의 높이에 비례하므로 O(log m) 시간에 완료됩니다.
정리
- 구조: 루트가 빈 완전 이진 트리, 총 노드 수 m + 1
- 조회: getMin / getMax를 O(1)에 수행
- 삽입·삭제: O(log m)에 수행
- 핵심 불변식: A1(형제 간 대소 관계), A2(왼쪽 방향 하한), A3(오른쪽 방향 상한)
이처럼 SMMH는 단순한 구조만으로 최솟값과 최댓값을 모두 상수 시간에 조회할 수 있으면서, 삽입과 삭제도 일반 힙과 동등한 로그 시간에 처리할 수 있는 실용적인 자료구조입니다.