최소-최대 힙(Min-Max Heap)은 최소(min) 레벨과 최대(max) 레벨이 번갈아 나타나는 완전 이진 트리(complete binary tree)로 정의됩니다. 이때 짝수 레벨은 0, 2, 4처럼 최소 레벨을 의미하고, 홀수 레벨은 1, 3, 5처럼 최대 레벨을 의미합니다.
이 글에서는 편의상 루트(root) 요소가 첫 번째 레벨, 즉 레벨 0에 위치한다고 가정합니다.
최소-최대 힙의 주요 특징
- 최소-최대 힙의 각 노드는 데이터 멤버(일반적으로 '키(key)'라고 함)를 가지며, 이 값은 해당 노드가 힙 내에서 어떤 순서를 갖는지 계산하는 데 사용됩니다.
- 루트 요소는 항상 최소-최대 힙 전체에서 가장 작은 값, 즉 최솟값입니다.
- 두 번째 레벨(홀수 레벨, 즉 최대 레벨)에 있는 두 요소 중 하나는 반드시 힙 전체의 최댓값입니다.
- y를 최소-최대 힙의 임의의 노드라고 할 때 다음 성질이 성립합니다.
- y가 최소(짝수) 레벨에 있다면, y.key는 y를 루트로 하는 서브트리(subtree)에 속한 모든 키 중에서 가장 작은 값입니다.
- y가 최대(홀수) 레벨에 있다면, y.key는 y를 루트로 하는 서브트리에 속한 모든 키 중에서 가장 큰 값입니다.
- 최소 레벨에 위치한 노드는 '최소 노드(min node)', 최대 레벨에 위치한 노드는 '최대 노드(max node)'라고 부릅니다.
최대-최소 힙(Max-Min Heap)
최대-최소 힙(Max-Min Heap)은 최소-최대 힙과 정반대의 구조를 가집니다. 이 힙에서는 가장 큰 값이 루트에 저장되고, 가장 작은 값은 루트의 자식 노드 중 하나에 저장됩니다. 즉, 우선순위의 방향만 뒤바뀐 형태로, 최댓값과 최솟값을 빠르게 조회해야 하는 상황에 따라 적절한 힙 구조를 선택할 수 있습니다.