Comparator을 사용하여 객체를 주문할 때 PriorityQueue을 사용하려고합니다.요소가 우선 순위를 변경하면 Java PriorityQueue가 업데이트됩니다.
쉽게 달성 할 수 있지만 개체 클래스 변수 (비교기가 우선 순위를 계산 함)는 초기 삽입 후에 변경 될 수 있습니다. 대부분의 사람들은 우선 순위 큐의 콤퍼레이터가 작동 할 때와 같이 개체를 제거하고 값을 업데이트 한 다음 다시 삽입하는 간단한 솔루션을 제안했습니다.
이 작업을 수행하기 위해 PriorityQueue 주변에 래퍼 클래스를 만드는 것 외에 다른 방법이 있습니까?
새 요소를 삽입 할 때 적절한 위치에 배치하여 큐가 작동하므로 제거하고 다시 삽입해야합니다. 이것은 대기열에서 빠져 나올 때마다 가장 우선 순위가 높은 요소를 찾는 것보다 훨씬 빠릅니다. 단점은 요소가 삽입 된 후에는 우선 순위를 변경할 수 없다는 것입니다. TreeMap에는 같은 제한이 있습니다 (삽입 후의 요소의 해시 코드가 변경 될 때도 중단되는 HashMap과 동일).
래퍼를 작성하려면 비교 코드를 대기열에서 대기열에서 대기열로 옮길 수 있습니다. 더 이상 대기열에 대기 시간을 정렬 할 필요가 없습니다. 왜냐하면 변경 사항을 허용하면 생성하는 순서가 신뢰할 수 없기 때문입니다.
그러나 성능이 저하되고 우선 순위를 변경하면 대기열에서 동기화하려고합니다. 우선 순위를 업데이트 할 때 동기화 코드를 추가해야하기 때문에 대기열에서 제외하고 대기열에 추가 할 수 있습니다 (두 경우 모두 대기열에 대한 참조가 필요함).
나는 그것을 변경하고 다시 삽입하는 것이 최선의 선택 인 것을 알 수있다. –
나는 그렇게 믿는다. 물론이 작업은 변경 작업을 수행하는 코드가 객체가 대기중인 대기열을 인식하는 경우에만 수행 할 수 있습니다. – Thilo
그래, 내 경우에는 그렇습니다. –
자바 구현이 있다면 나도 몰라,하지만 당신은 많이 키 값을 변경하는 경우, 당신이 가지고있는 Fibonnaci 힙을 사용할 수 있습니다 O (1) 상각 비용 감소의 키 값 일반 힙처럼 O (log (n))가 아닌 힙의 항목.
JDK에는 FibonacciHeap이 없지만 제 3 자로부터 존재합니다. 객체가 큐에 추가되면 우선 순위가 높아질 수 있으므로 O (1)을 사용하여 구현을 알면 두 요소를 바꿀 수 있습니까? 감소 기능과 같은 아니면 O (1)과 O (log (n))를 취하는 PriorityQueue 삭제 및 재 삽입 대신에 요소를 교체하여 구현으로 쉽게 달성 할 수 있습니까? –
값을 변경하면 의 직접 제어를 사용하는지 여부에 따라 크게 달라질 수 있습니다.
값이 변경된 것을 알고 있으면 제거하고 다시 삽입 할 수 있습니다. 실제로 제거하려면 힙을 선형 스캔해야하므로 비용이 많이 듭니다. 또한이 상황에서는 UpdatableHeap 구조 (주식 Java가 아님)를 사용할 수 있습니다. 본질적으로 해시 맵에서 요소의 위치를 추적하는 힙입니다. 이 방법은 요소의 우선 순위가 변경되면 힙을 복구 할 수 있습니다. 셋째, 똑같은 피보나치 힙을 찾을 수 있습니다.
업데이트 속도에 따라 매번 선형 스캔/빠른 선택/빠른 선택이 작동 할 수도 있습니다. 특히 pull 초 이상의 업데이트가있는 경우 이것이 가장 좋은 방법입니다. QuickSelect는 업데이트 일괄 처리 및 일괄 처리 일괄 처리가있는 경우에 가장 적합합니다.
다음과 같은 유용한 질문이 유용 할 수 있습니다. http://stackoverflow.com/questions/714796/priorityqueue-heap-update – perimosocordiae
큰 감사, 이전에 그 질문을 보지 못했습니다. –