목록자료구조 (1)
장난감 연구소
대칭 최소-최대 힙(SMMH)
대칭 최대-최소 힙(SMMH, symmetric min-max heap) 은 양쪽 끝 우선순위 큐를 표현할 수 있는 자료구조이다. 양쪽 끝 우선순위 큐(double-ended priority queue)는 일반적인 우선순위 큐와 달리 최소 우선순위 원소의 반환과 삭제, 최대 우선순위 원소의 반환과 삭제를 동시에 지원하는 자료구조이다. SMMH는 루트를 제외한 노드들이 하나의 원소를 갖는 완전 이진 트리이다. 루트는 공백이고, 각 노드는 아래 조건을 만족한다. 임의의 노드 N의 왼쪽 자식은 N의 서브트리의 원소 중 최소 원소를 갖는다. (존재한다면) 노드 N의 오른쪽 자식은 N의 서브트리의 원소 중 최대 원소를 갖는다. (존재한다면) 위 그림은 SMMH의 예를 보여준다. 노드 N을 10을 가진 노드라 할 ..
자료구조
2022. 6. 16. 23:06