각 객체가 (key, priority) 즉 (0, 3), (5, 7) 형식의 양식을 가지고 있다고 가정합니다. x와 y 두 개의 숫자가 있다고 가정 해보십시오. x와 y 사이에 키가있는 가장 우선 순위가 높은 객체를 반환하는 데 사용할 데이터 구조는 무엇입니까? 우선 순위 큐는 좋은 해결책이 될 수 있다고 생각하지만 주어진 범위에서 가장 우선 순위가 높은 개체를 반환하도록 수정하는 방법을 모른다.범위 쿼리가있는 우선 순위 대기열
이진 탐색 트리로 시작하여 하위 트리에 우선 순위가 가장 높은 우선 순위 노드 인 노드에 두 필드를 추가합니다 (이 기능을 수행하는 방법에 대한 자세한 내용은 CLRS 14 장 참조) .
이제 범위 쿼리를 수행하려면 현재 노드의 키가 범위에 속할 때까지 정상적으로 검색을 시작하십시오. 해당 노드를 검사하고 다음 절차의 대칭 변형을 사용하여 현재 노드의 왼쪽 및 오른쪽 하위 트리 인 범위에서 우선 순위가 가장 높은 노드를 포함하는 O (log n) 후보를 식별합니다. 다음 절차는 왼쪽 하위 트리에 대한 절차입니다.
루트가 범위 내에 있으면 노드에서 캐시 된 오른쪽 하위 트리의 우선 순위가 가장 높은 노드와 함께 가장 높은 우선 순위로 간주합니다. 왼쪽 하위 트리를 계속하십시오. 루트가 범위 내에 있지 않으면 오른쪽 하위 트리를 계속합니다.
"O (log n) 후보를 식별하는"트리 균형이 보장되는 것은 무엇입니까? –
@ CLRS 읽기 14 장 -이 기능 보강은 순환 후 시간 O (1)에 복원 할 수있는 형식이므로 균형 이진 검색 트리와 함께 작동합니다. –
이 문제를 RMQ (Range Minimum/Maximum Query)라고합니다.
귀하의 경우에 사용할 최상의 데이터 구조는 Segment Tree입니다.
처음에는 올바르게 시작하기가 힘들지 만 계속 시도하기 때문에 문제가 정확히 해결됩니다.
최소/최대 우선 순위에 대한 제한을 명확히 해 주실 수 있습니까? O (max -min) 메모리를 사용하는 솔루션이 있습니까? –