DEPQ(양방향 우선 순위 대기열) 또는 양방향 힙은 우선 순위 대기열 또는 힙과 같은 데이터 구조로 정의되지만 저장된 키 또는 항목의 일부 순서에 따라 최대값과 최소값을 모두 효율적으로 제거할 수 있습니다. 구조. 우선 순위 또는 값과 연결된 DEPQ의 모든 요소입니다. DEPQ에서는 오름차순 및 내림차순으로 요소를 제거하거나 제거할 수 있습니다.
작업
양방향 우선 순위 대기열은 다음 작업으로 구성됩니다.
isEmpty()
이 함수는 DEPQ가 비어 있는지 확인하고 비어 있으면 true를 반환합니다.
크기()
이 함수는 DEPQ에 있는 총 요소 수를 반환합니다.
getMin(y)
이 함수는 우선 순위가 가장 낮은 요소 y를 반환하는 역할을 합니다.
getMax(y)
이 함수는 우선 순위가 가장 높은 요소 y를 반환하는 역할을 합니다.
넣다(y)
이 함수는 DEPQ에 요소 y를 삽입하는 역할을 합니다.
최소(y) 제거
이 함수는 최소 우선순위로 요소 y를 제거하고 이 요소를 반환하는 역할을 합니다.
removeMax(y)
이 함수는 최대 우선순위로 요소 y를 제거하고 이 요소를 반환하는 역할을 합니다.
구현
이중 종단 우선 순위 대기열은 균형 이진 검색 트리(가장 작은 요소와 가장 큰 요소가 각각 가장 왼쪽 및 가장 오른쪽 리프로 처리됨)에서 구축하거나 형성하거나 최소-최대 힙 및 페어링 힙과 같은 특수 데이터 구조를 구현할 수 있습니다.
일반 우선 순위 대기열에서 이중 종료 우선 순위 대기열에 도달하는 일반적인 방법은 다음과 같습니다.
이중 구조 방식
이 방법에 따르면 최소 및 최대에 대한 두 가지 다른 우선 순위 대기열이 설정되거나 유지됩니다. 두 우선 순위 대기열의 동일한 요소가 통신 포인터의 도움으로 표시되거나 표시됩니다.
여기서 최소, 최대 요소는 각각 min heap과 max heap의 루트 노드에 포함된 값으로 표시됩니다.
최소 요소 제거 − 최소 힙에서 removemin(), 최대 힙에서 remove(노드 값)을 수행합니다. 여기서 노드 값은 최대 힙에서 해당 노드의 값으로 정의됩니다.
최대 요소 제거 − 최대 힙에서 removemax()를 수행하고 최소 힙에서 remove(노드 값)을 수행합니다. 여기서 노드 값은 최소 힙에서 해당 노드의 값으로 정의됩니다.
총 서신
요소의 절반은 최소 우선 순위 대기열에 있고 나머지 절반은 최대 우선 순위 대기열에 있습니다. 최소 우선 순위 대기열의 각 요소는 최대 우선 순위 대기열의 요소와 일대일로 대응합니다. DEPQ의 요소 수가 홀수 값을 나타내는 경우 요소 중 하나는 버퍼, 즉 특정 저장 영역에 유지됩니다. 최소 우선 순위 대기열에 있는 모든 요소의 우선 순위는 최대 우선 순위 대기열에 있는 해당 요소보다 작거나 같습니다.
리프 서신
이 방법에 따르면 최소 및 최대 우선 순위 큐의 리프 요소만 해당 일대일 쌍을 형성합니다. 잎이 아닌 요소가 일대일 대응 쌍에 있을 필요는 없습니다.
간격 힙
위에서 언급한 대응 방법 외에도 DEPQ는 간격 힙을 완벽하게 구현하여 얻을 수 있습니다. 간격 힙은 각 노드가 두 개의 요소로 구성된 포함된 최소-최대 힙과 같습니다. 다음과 같은 완전한 이진 트리로 정의됩니다. -
- 왼쪽 요소는 항상 오른쪽 요소보다 작거나 같습니다.
- 두 요소 모두 닫힌 간격을 정의하거나 지정합니다.
- 루트를 제외한 모든 노드가 나타내는 간격은 상위 노드의 하위 간격으로 표시됩니다.
- 왼쪽의 요소는 최소 힙을 정의하거나 나타냅니다.
- 오른쪽에 있는 요소는 최대 힙을 정의하거나 나타냅니다.