이중 힙
remove(aNode) 작업의 효율적인 구현을 제공하는 단일 종단형 우선 순위 대기열(PQ) 데이터 구조에서 효율적인 DEPQ(Double Ended Priority Queue) 데이터 구조에 도달하는 일반적인 방법의 존재(이 작업은 노드 aNode를 제거합니다. PQ). 이러한 방법 중 가장 간단한 이중 구조 방법은 동일한 요소를 구성하는 최소 PQ와 최대 PQ의 노드 간의 대응 포인터와 관련된 모든 DEPQ 요소의 최소 PQ와 최대 PQ를 모두 추적합니다.
그림 A는 요소 7, 8, 3, 6, 5에 대한 이중 힙 구조를 표시합니다. 대응 포인터는 빨간색 화살표로 표시됩니다.
그림 A:이중 힙
그림에는 최소 힙과 최대 힙 모두에 저장된 각 요소가 표시되지만 두 힙 중 하나에만 각 요소를 저장해야 합니다.
isEmpty 및 크기 작업은 DEPQ의 요소 수를 추적하는 가변 크기를 구현하여 적용됩니다. 최소 요소는 최소 힙의 루트에 있고 최대 요소는 최대 힙의 루트에 있습니다. 요소 A를 삽입하려면 최소 및 최대 힙 모두에 A를 삽입한 다음 최소 및 최대 힙에서 A의 위치 사이에 대응 포인터를 설정합니다. 최소 요소를 제거하기 위해 최소 힙에서 removeMin을 수행하고 최대 힙에서 제거된 요소에 대한 해당 노드가 aNode인 remove(aNode)를 수행합니다. 최대 요소는 유사한 방식으로 제거됩니다.
전체 및 리프 대응
전체 및 리프 대응은 보다 정교한 대응 기술입니다. 이 두 기술 모두에서 요소의 절반은 최소 PQ에 있고 나머지 절반은 최대 PQ에 있습니다. 요소의 개수가 홀수이면 하나의 요소가 버퍼에 저장됩니다. 이 버퍼링된 요소는 PQ의 구성원이 아닙니다. 전체 대응 기술에서 최소 PQ의 각 요소 x는 최대 PQ의 고유한 요소 y와 쌍을 이룹니다. (x, y)는 우선순위(x) <=우선순위(y)
와 같은 해당 요소 쌍입니다.그림 B는 11개의 요소 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11에 대한 총 대응 힙을 표시합니다. 요소 10은 버퍼에 있습니다. 해당 쌍은 빨간색 화살표로 표시됩니다.
그림 B:총 통신 힙
리프 대응 기술에서 최소 및 최대 PQ의 각 리프 요소는 해당 쌍의 일부가 되어야 합니다. 잎이 아닌 요소는 해당 쌍에 있을 필요가 없습니다. 그림 C는 리프 대응 힙을 표시합니다.
그림 C:리프 대응 힙
전체 및 리프 대응 구조는 이중 구조보다 적은 공간을 필요로 합니다. 그러나 전체 및 리프 대응 구조에 대한 DEPQ 알고리즘은 이중 구조에 대한 알고리즘보다 복잡합니다. 세 가지 대응 기술 중 리프 대응이 가장 빠른 DEPQ 대응 구조입니다.
설명된 대응 기술 중 하나를 구현하면 힙, 높이 편향 좌파 트리 및 페어링 힙에서 DEPQ 구조에 도달할 수 있습니다. 이러한 DEQP 구조에서 작업 put(x), removeMin() 및 removeMax()는 O(log n) 시간을 소비합니다(n은 DEPQ의 요소 수, 힙 쌍의 경우 분할 상환 복잡성임). 나머지 DEPQ 작업은 O(1) 시간을 소비합니다.