대응(Correspondence) 기반 데이터 구조란?
총 대응(total correspondence)과 리프 대응(leaf correspondence)은 양단 우선순위 큐(DEPQ, Double-Ended Priority Queue)를 구현하기 위한 보다 정교한 대응 기법입니다. 두 기법 모두 전체 원소의 절반은 최소 우선순위 큐(min PQ)에, 나머지 절반은 최대 우선순위 큐(max PQ)에 배치합니다. 만약 원소의 개수가 홀수라면, 하나의 원소는 버퍼에 저장되며 이 버퍼의 원소는 어느 쪽 PQ에도 속하지 않습니다.
총 대응(Total Correspondence)
총 대응 기법에서는 min PQ의 각 원소 x가 max PQ의 서로 다른 원소 y와 하나씩 짝을 이룹니다. 이때 (x, y)는 priority(x) <= priority(y) 조건을 만족하는 대응 쌍(corresponding pair)이라고 합니다.
아래 그림 E는 11개의 원소 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11로 구성된 총 대응 힙을 보여줍니다. 이 예제에서 원소 10은 버퍼에 저장되어 있으며, 빨간색 화살표가 각 대응 쌍의 관계를 나타냅니다.
그림 E: 총 대응 힙
리프 대응(Leaf Correspondence)
리프 대응 기법에서는 min PQ와 max PQ의 각 리프(leaf) 원소가 반드시 어떤 대응 쌍에 속해야 한다는 점이 특징입니다. 반면, 리프가 아닌 내부(internal) 원소들은 대응 쌍에 포함될 필요가 없습니다. 아래 그림 F는 리프 대응 힙의 예를 보여줍니다.
그림 F: 리프 대응 힙
세 가지 대응 기법의 비교
총 대응 구조와 리프 대응 구조는 이중(dual) 구조에 비해 더 적은 메모리 공간을 필요로 한다는 장점이 있습니다. 다만, 이러한 구조들을 위한 DEPQ 알고리즘은 이중 구조의 알고리즘보다 구현 난이도가 높고 복잡합니다. 세 가지 대응 기법 가운데서는 리프 대응이 가장 빠른 성능을 제공하는 DEPQ 대응 구조로 평가됩니다.