우선 순위 대기열과 비슷하지만 하한과 같은 구조가 있습니다.

Question

구조를 삽입하여 요소를 삽입하고 제거 할 수있는 구조를 유지하고 싶습니다. 구조는 항상 우선 순위 대기열처럼 정렬되어 있습니다. 주어진 수이고, 모든 연산은 대수 시간이다.

lower_bound, upper_bound 또는 단지 바이너리 검색이있을 수 있지만 priority_queue에서는 바이너리 검색을 차단하는 이유는 인덱스가있는 요소에 액세스 할 수 없기 때문에 첫 번째 요소 만 액세스 할 수 있기 때문입니다.

Answer 1

나는 당신이 order statistics tree, 모든 일반 BST 작업을 지원하는 증강 BST 찾고있는 생각과 같은 노드 기반 힙이 작업을 수행 할 수 있습니다 O (log n)은 두 개의 다른 문자와 함께 표시됩니다.

• rank (elem) : 반환 된 색인 elem은 정렬 된 순서에서 차지합니다.
• index (k) : 인덱스 k가 주어진 경우 정렬 된 순서로 해당 인덱스에있는 요소를 반환합니다.

위의 두 작업은 O (log n) 시간에 실행되므로 매우 빠릅니다.

주문 통계 트리를 우선 순위 대기열로 처리 할 수 ​​있습니다. 삽입은 일반적인 BST 삽입으로 작동하고 가장 낮은/가장 높은 요소를 추출하기 위해 나무에서 가장 작은/가장 큰 요소를 제거합니다. 그러면 트리의 왼쪽 또는 오른쪽 등뼈를 걷고 O (log n) 시간 내에 할 수 있습니다 .

Answer 2

우선 순위 대기열은 항목을 정렬 된 순서로 유지하지 않습니다. 최소한, 일반적으로는 아닙니다. 우선 순위 대기열을 사용하면 시퀀스의 다음 항목을 빠르게 얻을 수 있습니다. 하지만 대기열에있는 다섯 번째 항목에 효율적으로 액세스 할 수는 없습니다.

• 큐를 구현하는 균형 이진 검색 트리를 사용

  난 당신이 효율적으로 키 항목에 액세스 할 수있는 우선 순위 큐를 구축하는 세 가지 방법을 알고. 모든 연산은 O (log n)이지만 일반적인 실행 시간은 바이너리 힙보다 느립니다.

• 힙 우선 순위 큐를 skip list으로 구현하십시오. 이것은 좋은 선택입니다. 필자는 일부 사람들이 건너 뛰기 목록 우선 순위 큐가 바이너리 힙을 능가한다고보고했습니다. [C++ 건너 뛰기 목록]을 검색하면 많은 구현이 반환됩니다.
• 인덱싱 된 바이너리 힙 (heap)이라고도하는 것은 또한 작동합니다. 기본적으로 해시 맵이나 사전을 바이너리 힙과 결합시킵니다. 맵은 key에 의해 인덱싱되고 그 값은 힙 배열에있는 항목의 인덱스를 포함합니다. 그러한 것은 건설하기가 어렵지 않고 매우 효과적입니다.
• 생각해 보면 어떤 유형의 힙에 대해서도 색인 된 버전을 만들 수 있습니다.

몇 가지 옵션이 있습니다. 나는 오히려 건너 뛰기 목록을 좋아하지만 나 자신의 마일리지는 다를 수 있습니다.

인덱스 된 바이너리 힙은 사전 (해시 맵)과 바이너리 힙을 유지하는 하이브리드 데이터 구조입니다. 간단히 작동 원리 :

사전 키는 힙에 넣은 항목을 검색하는 데 사용하는 필드입니다. 값은 정수입니다. 힙에있는 해당 항목의 인덱스입니다.

힙 자체는 배열에 구현 된 표준 바이너리 힙입니다. 유일한 차이점은 힙의 한 위치에서 다른 위치로 항목을 이동할 때마다 해당 위치를 사전에서 업데이트한다는 것입니다. 따라서 예를 들어 두 항목을 서로 바꾸면 배열의 항목 자체뿐만 아니라 사전에 저장된 항목의 위치도 바꿔야합니다. 예 :

heap is an array of string references 
dict is a dictionary, keyed by string 

swap (a, b) 
{ 
    // swap item at heap[a] with item at heap[b] 
    temp = heap[a] 
    heap[a] = heap[b] 
    heap[b] = temp 
    // update their positions in the dictionary 
    dict[heap[a]] = b 
    dict[heap[b]] = a 
} 

표준 바이너리 힙 구현의 매우 간단한 수정입니다. 항목을 이동할 때마다 위치를 업데이트하는 데주의해야합니다.

또한 등 페어링 힙, 피보나치 힙, 기울기 힙,