이중 엔드 priority 큐

Double-ended priority queue
더블 엔드 큐와 혼동하지 마십시오.

컴퓨터 과학에서 DEPQ([1]double-end priority queue) 또는 이중 엔드 힙은[2] priority 큐 또는 힙과 유사한 데이터 구조이지만 구조에 저장된 키(항목)의 순서에 따라 최대값과 최소값을 모두 효율적으로 제거할 수 있습니다.DEPQ의 모든 요소에는 priority 또는 값이 있습니다.DEPQ에서는 오름차순과 [3]내림차순으로 요소를 제거할 수 있습니다.

운용

이중 엔드 priority 큐에는 다음 조작이 있습니다.

is Empty()
DEPQ가 비어 있는지 확인하고 비어 있으면 true를 반환합니다.
사이즈()
DEPQ에 존재하는 요소의 총 수를 반환합니다.
get Min()
우선순위가 가장 낮은 요소를 반환합니다.
getMax()
priority가 가장 높은 요소를 반환합니다.
put(x)
요소 x를 DEPQ에 삽입합니다.
remove Min()
최소 우선순위의 요소를 제거하고 이 요소를 반환합니다.
remove Max()
최대 priority를 가진 요소를 삭제하고 이 요소를 반환합니다.

같은 priority를 가지는 2개의 요소에 대해서 연산을 실시하는 경우는, 최초로 삽입된 요소를 선택한다.또한 DEPQ에 [4]삽입된 요소의 priority를 변경할 수 있습니다.

실행

이중 엔드 priority 큐는 균형 잡힌 바이너리 검색 트리(최소 및 최대 요소는 각각 왼쪽 끝과 오른쪽 끝)에서 구축하거나 최소-최대 힙 및 쌍으로 구성된 힙과 같은 특수 데이터 구조를 사용하여 구축할 수 있습니다.

일반 priority 큐에서 더블 엔드 priority 큐에 도달하는 일반적인 방법은 다음과 같습니다.[5]

이중구조법

DEPQ의 [1]멤버로서 14,12,4,10,8을 가지는 듀얼 구조.

이 방법에서는 min과 max의 2개의 priority 큐가 유지됩니다.양쪽 PQ의 동일한 요소는 대응 포인터의 도움을 받아 표시됩니다.
여기서 최소 및 최대 요소는 각각 최소 힙과 최대 힙의 루트 노드에 포함되는 값이다.

  • min 요소 삭제: min 힙에서 removemin()을 수행하고 max 힙에서 remove(node value)를 수행합니다.여기서 node value는 max 힙 내의 대응하는 노드 값입니다.
  • max 요소 삭제: max 힙에서 removemax()를 실행하고 min 힙에서 remove(node value)를 수행합니다.여기서 node value는 min 힙 내의 대응하는 노드 값입니다.

총 대응

요소 11을 [1]버퍼로 하는 요소 3, 4, 5, 6, 7, 8, 9, 10, 11의 합계 대응 힙이다.

요소의 절반은 최소 PQ에 있고 나머지 절반은 최대 PQ에 있습니다.최소 PQ 내의 각 요소는 최대 PQ 내의 요소와 일대일 대응 관계를 가진다.DEPQ 내의 요소 수가 홀수일 경우 요소 중 하나가 [1]버퍼에 유지됩니다.최소 PQ 내의 모든 요소의 priority는 최대 PQ 내의 대응하는 요소 이하가 됩니다.

잎 대응

위와 [1]같은 요소에 대한 리프 대응 힙입니다.

전체 대응과는 대조적으로 이 방법에서는 min과 max PQ의 리프 요소만이 대응하는 일대일 쌍을 형성한다.잎이 아닌 요소가 일대일 대응 [1]쌍에 있을 필요는 없습니다.DEPQ 내의 요소 수가 홀수일 경우 요소 중 하나가 [1]버퍼에 유지됩니다.

간격 힙

인터벌 힙을 사용한 DEPQ 구현

상기 대응방법과는 별도로 DEPQ는 인터벌 [6]힙을 이용하여 효율적으로 얻을 수 있다.인터벌 힙은 각 노드에 2개의 요소가 포함되어 있는 임베디드 min-max 힙과 같습니다.이 트리는 완전한 바이너리 [6]트리에는 다음이 포함됩니다.

  • 왼쪽 요소가 오른쪽 요소보다 작거나 같습니다.
  • 두 요소 모두 닫힌 간격을 정의합니다.
  • 루트를 제외한 모든 노드가 나타내는 간격은 부모 노드의 하위 간격입니다.
  • 왼쪽 요소는 최소 힙을 정의합니다.
  • 오른쪽 요소는 최대 힙을 정의합니다.

요소의 수에 따라 두 가지 경우가 있습니다[6].

  1. 짝수 요소:이 경우 각 노드에는 p와 q라는2개의 요소가 포함되어 있습니다.각 노드는 [p, q]의 간격으로 표시됩니다.
  2. 홀수 요소 수:이 경우 마지막 노드를 제외한 각 노드에는 간격 [p, q]로 표시되는2개의 요소가 포함되어 마지막 노드에는 단일 요소가 포함되어 간격 [p, p]로 표시됩니다.

요소 삽입

간격 힙에 이미 존재하는 요소의 수에 따라 다음과 같은 경우가 있습니다.

  • 홀수 요소 수:간격 힙 내의 요소 수가 홀수일 경우 새 요소가 먼저 마지막 노드에 삽입됩니다.그런 다음 위의 노드 요소와 연속적으로 비교하여 위에서 설명한 바와 같이 간격 힙에 필수적인 기준을 충족하도록 테스트합니다.요소가 어느 기준도 충족하지 못할 경우 모든 조건이 [6]충족될 때까지 마지막 노드에서 루트로 이동합니다.
  • 짝수 요소:요소의 수가 짝수인 경우 새 요소를 삽입하기 위해 추가 노드가 생성됩니다.요소가 부모 간격의 왼쪽에 있으면 최소 힙에 있는 것으로 간주되며, 요소가 부모 간격의 오른쪽에 있으면 최대 힙에 있는 것으로 간주됩니다.또, 연속적으로 비교되어 인터벌 히프의 모든 조건이 충족될 때까지, 마지막 노드에서 루트로 이동한다.요소가 부모 노드 자체의 간격 내에 있는 경우 프로세스는 거기서 정지되고 요소의 이동은 [6]이루어지지 않습니다.

요소를 삽입하는 데 필요한 시간은 모든 조건을 충족하는 데 필요한 이동 횟수에 따라 달라지며 O(log n)입니다.

요소 삭제

  • 최소 요소:간격 힙에서 최소 요소는 루트 노드 왼쪽에 있는 요소입니다.이 요소는 삭제되어 반환됩니다.루트 노드의 좌측에 작성된 빈자리를 채우기 위해 마지막 노드의 요소가 삭제되고 루트 노드에 다시 삽입됩니다.그런 다음 이 요소를 내림차순 노드의 모든 왼쪽 요소와 연속적으로 비교하고 간격 힙의 모든 조건이 충족되면 프로세스가 중지됩니다.노드 내의 좌측 요소가 어느 단계에서 우측 요소보다 커졌을 경우, 2개의 요소를 교환하고[6] 나서, 한층 더 비교를 실시한다.마지막으로 루트 노드에는 왼쪽에 최소 요소가 다시 포함됩니다.
  • 최대 요소:간격 힙에서 최대 요소는 루트 노드의 오른쪽에 있는 요소입니다.이 요소는 삭제되어 반환됩니다.루트 노드의 오른쪽에 생성된 빈자리를 채우기 위해 마지막 노드의 요소가 제거되고 루트 노드에 다시 삽입됩니다.추가 비교는 위에서 설명한 것과 유사한 기준으로 수행됩니다.마지막으로 루트 노드 우측에 max 요소가 다시 포함됩니다.

따라서 간격 힙을 사용하면 루트 간에 효율적으로 이동하는 최소 및 최대 요소를 모두 제거할 수 있습니다.따라서 DEPQ는 인터벌히프 요소가 DEPQ 내의 요소의 priority인 인터벌히프에서 취득할[6] 수 있습니다.

시간의 복잡성

간격 힙

N개의 요소로 구성된 Interval hump를 사용하여 DEPQ를 구현한 경우, 다양한 함수의 시간 복잡도는 아래 표에 나타나[1] 있습니다.

작동 시간의 복잡성
초기화() O(n)
is Empty ( ) O(1)
getmin() O(1)
getmax() O(1)
사이즈( ) O(1)
삽입(x) O(log n)
remove Min() O(log n)
removeMax() O(log n)

페어링 힙

DEPQ를 n개의 요소로 구성된 힙 또는 페어링 힙을 사용하여 구현할 경우,[1] 다양한 기능의 시간 복잡도를 아래 표에 나타냅니다.쌍체 힙의 경우 상각 복잡도입니다.

작동 시간의 복잡성
is Empty ( ) O(1)
getmin() O(1)
getmax() O(1)
삽입(x) O(log n)
removeMax() O(log n)
remove Min() O(log n)

적용들

외부 정렬

이중 엔드 priority 큐의 적용 예로는 외부 정렬이 있습니다.외부적으로는 컴퓨터의 메모리에 저장할 수 있는 것보다 많은 요소가 있습니다.정렬할 요소는 처음에는 디스크에 있고 정렬된 시퀀스는 디스크에 남아 있어야 합니다.외부 빠른 정렬은 다음과 같이 DEPQ를 사용하여 구현됩니다.

  1. 내부 DEPQ에 맞는 요소를 최대한 많이 읽습니다.DEPQ의 요소는 최종적으로 요소의 중간 그룹(피봇)이 됩니다.
  2. 나머지 요소를 읽습니다.다음 요소가 DEPQ에서 가장 작은 요소인 경우 이 다음 요소를 왼쪽 그룹의 일부로 출력합니다.다음 요소가 DEPQ에서 가장 큰 요소인 경우 이 다음 요소를 오른쪽 그룹의 일부로 출력합니다.그렇지 않으면 DEPQ에서 max 또는 min 요소를 삭제합니다(임의 또는 교대로 선택 가능).max 요소가 삭제되면 오른쪽 그룹의 일부로 출력합니다.그렇지 않으면 삭제된 요소를 왼쪽 그룹의 일부로 출력하고 새로 입력된 요소를 DEPQ에 삽입합니다.
  3. DEPQ의 요소를 정렬된 순서로 중간 그룹으로 출력합니다.
  4. 왼쪽 및 오른쪽 그룹을 재귀적으로 정렬합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d e f g h i 자바에서의 데이터 구조, 알고리즘 및 애플리케이션: 더블 엔드 priority 큐, Sartaj Sahni, 1999.
  2. ^ Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. p. 211. ISBN 9780521880374.
  3. ^ "Depq - Double-Ended Priority Queue". Archived from the original on 2012-04-25. Retrieved 2011-10-04.
  4. ^ "depq".
  5. ^ C++ 데이터 구조의 기초 - Ellis Horowitz, Sartaj Sahni 및 Dinesh Mehta
  6. ^ a b c d e f g http://www.mhhe.com/engcs/compsci/sahni/enrich/c9/interval.pdf[베어 URL PDF]