SMMH(대칭 최소-최대 힙)는 루트를 제외한 각 노드에 정확히 하나의 요소가 있는 완전한 이진 트리로 정의됩니다. SMMH의 루트는 비어 있고 SMMH의 총 노드 수는 m + 1입니다. 여기서 m은 요소 수입니다.
y를 SMMH의 임의의 노드라고 하자. 요소(y)를 y에 뿌리를 둔 하위 트리의 요소로 설정하지만 y의 요소(있는 경우)는 제외합니다. 요소(y) j=∅라고 가정합니다. y는 다음 속성을 충족합니다.
- y의 왼쪽 자식은 elements(y)에서 최소 요소를 가집니다.
- y의 오른쪽 자식(있는 경우)은 elements(y)에서 최대 요소를 가집니다.
그림 1은 12개의 요소가 있는 SMMH의 예를 보여줍니다.
y가 81인 노드를 나타낼 때 elements(y) ={7, 15, 31, 41}; y의 왼쪽 자식은 elements(y)에서 최소 요소 6을 갖습니다. y의 오른쪽 자식은 elements(y)에서 최대 41개의 요소를 가집니다. 이 SMMH의 모든 노드 y가 명시된 속성을 충족하는지 확인할 수 있습니다.
SMMH는 완전한 이진 트리로 표시되기 때문에 완전한 이진 트리를 배열로 매핑하는 표준을 구현하는 암시적 데이터 구조로 저장됩니다. m =1일 때 최소 및 최대 요소는 동일하며 SMMH 루트의 왼쪽 자식에 포함됩니다.
m> 1일 때 최소 요소는 루트의 왼쪽 자식에 있고 최대는 루트의 오른쪽 자식에 있습니다. 따라서 getMin 및 getMax 작업은 O(1) 시간을 소비합니다.
다음이 참이면 루트가 비어 있고 다른 모든 노드에 하나의 요소가 있는 m + 1-노드 완전 이진 트리가 SMMH임을 쉽게 알 수 있습니다. -
A1 - 오른쪽 형제가 있는 모든 노드 y에 대해 y의 요소는 y의 오른쪽 형제보다 작거나 같습니다.
A2 - 조부모가 있는 모든 노드 y에 대해 조부모의 왼쪽 자식 요소는 y의 요소보다 작거나 같습니다.
A3 - 조부모가 있는 모든 노드 y에 대해 조부모의 오른쪽 자식 요소는 y의 요소보다 크거나 같습니다.
속성 A1이 노드 y에서 충족되면 y에서 A2와 A3 중 최대 하나만 위반될 수 있습니다. 속성 A1에서 A3을 구현하면 요소를 삽입하고 제거하는 간단한 알고리즘에 도달합니다. 이러한 알고리즘은 최소 및 최대 힙에 대해 해당 알고리즘을 간단하게 적용한 것입니다. 복잡도는 O(log m)입니다.
여기에서 삽입 작업을 지정합니다. 그림 1의 SMMH에 3을 삽입한다고 가정합니다. SMMH는 완전한 이진 트리이므로 그림 2에 표시된 위치에 SMMH에 새 노드를 추가해야 합니다. 새 노드는 B로 레이블이 지정됩니다.
이 예에서 B는 빈 노드를 나타냅니다. 이제 노드 B에 3이 삽입됩니다.