C ++에서 키 업데이트로 최소 우선 순위 대기열을 사용하는 가장 쉬운 방법

C ++에서 키 업데이트로 최소 우선 순위 대기열을 사용하는 가장 쉬운 방법

---

때로는 프로그래밍 대회 등에서 Dijkstra 알고리즘 등을 구현하기 위해 감소 키가있는 최소 우선 순위 대기열의 간단한 작업 구현이 필요합니다. 저는 종종 set <pair <key_value, ID>> 및 배열 (mapping ID-> key_value)을 사용합니다. ) 함께 달성합니다.

• 집합에 요소를 추가하는 데 O (log (N)) 시간이 걸립니다. N 개의 요소로 우선 순위 큐를 구축하려면 세트에 하나씩 추가하기 만하면됩니다. 총 O (N log (N)) 시간이 걸립니다.

• min key_value가있는 요소는 단순히 집합의 첫 번째 요소입니다. 가장 작은 요소를 프로빙하는 데는 O (1) 시간이 걸립니다. 제거하는 데 O (log (N)) 시간이 걸립니다.

• 일부 ID = k가 집합에 있는지 테스트하려면 먼저 배열에서 key_value = v_k를 찾은 다음 집합에서 요소 (v_k, k)를 검색합니다. O (log (N)) 시간이 걸립니다.

• 일부 ID = k의 key_value를 v_k에서 v_k '로 변경하려면 먼저 배열에서 key_value = v_k를 찾은 다음 세트에서 요소 (v_k, k)를 검색합니다. 다음으로 세트에서 해당 요소를 제거한 다음 요소 (v_k ', k)를 세트에 삽입합니다. 그런 다음 배열도 업데이트합니다. O (log (N)) 시간이 걸립니다.

위의 접근 방식이 작동하지만 대부분의 교과서는 바이너리 힙을 빌드하는 시간이 O (N)에 불과하므로 일반적으로 바이너리 힙을 사용하여 우선 순위 큐를 구현하는 것이 좋습니다. 바이너리 힙을 사용하는 C ++의 STL에 우선 순위 큐 데이터 구조가 내장되어 있다고 들었습니다. 그러나 해당 데이터 구조의 key_value를 업데이트하는 방법을 모르겠습니다.

C ++에서 키 업데이트와 함께 최소 우선 순위 대기열을 사용하는 가장 쉽고 효율적인 방법은 무엇입니까?

---

Darren이 이미 말했듯이, std::priority_queue요소의 우선 순위를 낮추는 수단이없고 현재 최소값 이외의 요소를 제거 할 수도 없습니다. 그러나 기본값 std::priority_queue은 ( , 및 ) std::vector의 표준 힙 함수를 사용하는 a 주변의 단순한 컨테이너 어댑터에 지나지 않습니다 . 따라서 Dijkstra (우선 순위 업데이트가 필요한 곳)의 경우 일반적으로 직접 수행하고 간단한 .<algorithm>std::push_heapstd::pop_heapstd::make_heapstd::vector

푸시는 O (log N) 연산입니다.

vec.push_back(item);
std::push_heap(vec.begin(), vec.end());

물론 N 개의 요소로부터 새로운 큐를 생성하기 위해, 우리는이 O (log N) 연산을 사용하여 모든 것을 밀어 붙이지 않고 (전체를 O (Nlog N) 만들기), 그냥 모두 벡터에 넣은 다음 간단한 O (엔)

std::make_heap(vec.begin(), vec.end());

min 요소는 간단한 O (1)입니다.

vec.front();

팝은 단순한 O (log N) 시퀀스입니다.

std::pop_heap(vec.begin(), vec.end());
vec.pop_back();

지금까지 이것은 std::priority_queue일반적으로 내부에서하는 일입니다. 이제 항목의 우선 순위를 변경하려면 항목을 변경하고 (항목 유형에 통합 될 수 있음) 시퀀스를 다시 유효한 힙으로 만들어야합니다.

std::make_heap(vec.begin(), vec.end());

나는 이것이 O (N) 연산이라는 것을 알고 있지만, 반면에 이것은 추가 데이터 구조를 사용하여 힙에서 항목의 위치를 ​​추적 할 필요가 없거나 항목 유형의 증가 (심지어 더 나쁜 경우)를 제거합니다. 그리고 로그 우선 순위 업데이트에 대한 성능 패널티는 실제로 사용의 용이성, std::vector(런타임에도 영향을 미치는) 의 간결하고 선형적인 메모리 사용, 그리고 종종 가장자리가 적은 그래프로 작업한다는 사실을 고려할 때 그리 크지 않습니다. (정점 수의 선형) 어쨌든.

모든 경우에 가장 빠른 방법은 아니지만 확실히 가장 쉬운 방법입니다.

편집 : 아, 그리고 표준 라이브러리는 최대 힙을 사용하기 >때문에 기본 <연산자 대신 우선 순위를 비교 하는 데 동등한 것을 사용해야합니다 (항목에서 가져옴) .

---

내 답변이 원래 질문에 대한 답변은 아니지만 OP의 의견 인 C ++ / Java (나와 같은)로 Dijkstra 알고리즘을 구현하려고 할 때이 질문에 도달하는 사람들에게 유용 할 수 있다고 생각합니다.

priority_queueC ++ (또는 PriorityQueueJava)에서는 decrease-key앞서 말했듯 이 작업을 제공하지 않습니다 . Dijkstra를 구현할 때 이러한 클래스를 사용하는 좋은 방법은 "지연 삭제"를 사용하는 것입니다. Dijkstra 알고리즘의 메인 루프는 우선 순위 대기열에서 처리 할 다음 노드를 추출하고 모든 인접 노드를 분석하여 결국 우선 순위 대기열에있는 노드의 최소 경로 비용을 변경합니다. 이것은 decrease-key해당 노드의 값을 업데이트하기 위해 일반적으로 필요한 지점 입니다.

트릭은 전혀 변경하지 않습니다 . 대신 해당 노드에 대한 "새 복사본"(새롭고 더 나은 비용 포함)이 우선 순위 대기열에 추가됩니다. 비용이 더 낮 으면 노드의 새 사본이 큐의 원본 사본보다 먼저 추출되므로 더 빨리 처리됩니다.

이 "지연 삭제"의 문제는 불량 비용이 더 높은 노드의 두 번째 복사본이 결국 우선 순위 대기열에서 추출된다는 것입니다. 그러나 이는 항상 더 나은 비용으로 두 번째로 추가 된 사본이 처리 된 후에 발생합니다. 따라서 우선 순위 대기열에서 다음 노드를 추출 할 때 기본 Dijkstra 루프가 수행해야하는 첫 번째 작업 은 해당 노드가 이전에 방문했는지 확인하는 것입니다 (이미 최단 경로를 알고 있음). 바로 그 순간에 우리가 "지연 삭제"를 할 것이고 요소는 단순히 무시되어야합니다.

이 솔루션은 메모리와 시간 모두에 비용이들 것입니다. 우선 순위 큐는 제거하지 않은 "데드 요소"를 저장하기 때문입니다. 그러나 실제 비용은 매우 적고이 솔루션을 프로그래밍하는 것은 IMHO가 누락 된 decrease-key작업 을 시뮬레이션하려는 다른 대안보다 쉽습니다 .

---

std::priority_queue클래스가 decrease-key스타일 작업 의 효율적인 구현을 허용 하지 않는다고 생각합니다 .

이를 지원하는 자체 바이너리 힙 기반 데이터 구조를 기본적 std::set으로 기반 우선 순위 큐에 대해 설명한 것과 매우 유사한 라인을 따라 롤링했습니다 .

• 의 value요소를 저장하는 정렬 된 바이너리 힙 pair<value, ID>과 ID -> heap_index. 힙 루틴 heapify_up, heapify_down등 내에서 매핑 배열이 요소의 현재 힙 위치와 동기화 상태를 유지하는지 확인해야합니다. 이것은 약간의 추가 O(1)오버 헤드를 추가합니다 .
• 여기에O(N) 설명 된 표준 알고리즘 에 따라 배열을 힙으로 변환 할 수 있습니다 .
• 루트 요소를 엿보는 것은 O(1)입니다.
• ID현재 힙에 있는지 확인 하려면 O(1)매핑 배열에서 조회 만하면 됩니다. 또한에 O(1)해당하는 요소를 엿볼 수 있습니다 ID.
• Decrease-key필요 O(1)룩업 다음에 매핑 배열 O(log(N))을 통해 힙에 대한 업데이 트를 heapify_up, heapify_down.
• 새 항목을 힙에 푸시하는 것은 힙에서 기존 항목을 O(log(N))팝하는 것과 같습니다.

따라서 점근 적 std::set으로 기반 데이터 구조에 비해 몇 가지 작업에 대해 런타임이 향상됩니다 . 또 다른 중요한 개선점은 이진 힙이 배열에 구현 될 수있는 반면 이진 트리는 노드 기반 컨테이너라는 것입니다. 바이너리 힙의 추가 데이터 지역 성은 일반적으로 향상된 런타임으로 변환됩니다.

이 구현과 관련된 몇 가지 문제는 다음과 같습니다.

• 정수 항목 만 허용 ID됩니다.
• ID0부터 시작하여 항목의 긴밀한 분포를 가정합니다 (그렇지 않으면 매핑 배열의 공간 복잡성이 폭발합니다!).

You could potentially overcome these issues if you maintained a mapping hash-table, rather than a mapping array, but with a little more runtime overhead. For my use, integer ID's have always been enough.

Hope this helps.

ReferenceURL : https://stackoverflow.com/questions/9209323/easiest-way-of-using-min-priority-queue-with-key-update-in-c