최소-최대 힙은 최소(또는 짝수) 및 최대(또는 홀수) 수준을 교대로 포함하는 완전한 이진 트리로 정의됩니다. 짝수 레벨은 예를 들어 0, 2, 4 등으로 표시되고 홀수 레벨은 1, 3, 5 등으로 표시됩니다.
다음 지점에서 루트 요소가 첫 번째 수준, 즉 0에 있다고 생각합니다.
최소-최대 힙의 예
최소-최대 힙의 기능
- 최소-최대 힙의 각 노드는 최소-최대 힙의 노드 순서를 계산하기 위해 값이 구현되는 데이터 멤버(보통 키라고 함)와 연결됩니다.
- 루트 요소는 최소-최대 힙의 최소 요소입니다.
- 최대(또는 홀수) 수준인 두 번째 수준의 두 요소 중 하나는 최소-최대 힙의 최대 요소입니다.
- y를 최소-최대 힙의 임의의 노드로 설정합니다.
- y가 최소(또는 짝수) 수준에 있으면 y.key는 루트 y가 있는 하위 트리의 모든 키 중에서 가장 작은 키입니다.
- y가 최대(또는 홀수) 수준에 있으면 y.key는 루트 y가 있는 하위 트리의 모든 키 중에서 가장 높은 키입니다.
- 최소(최대) 수준의 노드는 최소(최대) 노드로 표시됩니다.
최대 최소 힙은 최소 최대 힙의 반대로 정의됩니다. 이러한 힙에서 가장 높은 값은 루트에 저장되고 최소값은 루트의 자식 중 하나에 저장됩니다.