remove(bNode) 작업의 효율적인 구현을 제공하는 단일 종단형 우선 순위 대기열(PQ) 데이터 구조에서 효율적인 DEPQ(Double Ended Priority Queue) 데이터 구조에 도달하는 일반적인 방법의 존재(이 작업은 노드 bNode를 제거합니다. PQ). 이러한 방법 중 가장 간단한 이중 구조 방법은 동일한 요소를 구성하는 최소 PQ와 최대 PQ의 노드 간의 대응 포인터와 관련된 모든 DEPQ 요소의 최소 PQ와 최대 PQ를 모두 유지합니다.
그림 D는 요소 7, 8, 3, 6, 5에 대한 이중 힙 구조를 표시합니다. 대응 포인터는 빨간색 화살표로 표시됩니다.
그림 D:이중 힙
그림에는 최소 힙과 최대 힙 모두에 저장된 각 요소가 표시되지만 두 힙 중 하나에만 각 요소를 저장해야 합니다.
isEmpty 및 크기 작업은 DEPQ의 요소 수를 추적하는 가변 크기를 구현하여 적용됩니다. 최소 요소는 최소 힙의 루트에 있고 최대 요소는 최대 힙의 루트에 있습니다. 요소 B를 삽입하려면 최소 및 최대 힙에 B를 삽입한 다음 최소 및 최대 힙에서 B의 위치 사이에 대응 포인터를 설정합니다. 최소 요소를 제거하기 위해 최소 힙에서 removeMin을 수행하고 최대 힙에서 제거(bNode가 제거된 요소에 해당하는 노드)인 remove(bNode)를 수행합니다. 최대 요소는 유사한 방식으로 제거됩니다.