java.util.PriorityQueue을 사용하면 시공시에 Comparator을 전달할 수 있습니다. 요소를 삽입 할 때, 그들은 비교 자에 의해 지정된 우선 순위에 따라 정렬됩니다.Java의 우선 순위 대기열
삽입 된 요소의 우선 순위가 변경되면 어떻게됩니까? PriorityQueue 요소는 언제 재주문합니까? 실제로 최소한의 우선 순위가없는 요소를 폴링 할 수 있습니까?
효율적인 우선 순위 업데이트를 허용하는 우선 순위 대기열의 구현이 있습니까?
삽입 될 때 순서가 발생하므로 요소를 제거하고 변경 한 다음 다시 삽입해야합니다. 여러 단계를 거치지 만 이 효율적이므로으로 충분할 수 있습니다. (O (n) 인 제거에 대한 주석을 방금 알았습니다.)
한 가지 문제점은 엘리먼트를 제거 할 때 다시 정렬된다는 것입니다.이 엘리먼트를 잠깐 다시 삽입하려는 경우 중복됩니다. 후에. 자신의 우선 순위 큐를 처음부터 구현하는 경우이 단계를 건너 뛰는 update()가있을 수 있지만 여전히 base에 의해 제공되는 remove() 및 add()로 제한되므로 Java 클래스 확장은 작동하지 않습니다.
을 다시 주문하지 마십시오. 새 항목을 넣을 정확한 위치를 찾기 위해 이진 검색을 시도하면 매우 혼란 스러울 수 있습니다.
일반적으로 해시 테이블에서 키를 구성하는 값을 변경하는 것과 마찬가지로 큐에있는 항목의 우선 순위를 나쁜 생각으로 변경하는 것이 일반적입니다.
일부 알고리즘 (예 : Dijkstra 's Algorithm)에서는 이미 대기열에있는 항목의 우선 순위를 변경할 수 있습니다. –
하지만 알림이 있어야합니다. 우선 순위가 변경되면 항목을 제거한 후 다시 추가하여 PriorityQueue의 도움을받지 않고 위조를 만들 수 있습니다. –
@Jon 내가 틀렸다면 정정 해 주겠다.하지만 제거는 sun의 구현을위한 O (n)이라고 생각한다. 결국 이것은 O (n log n)가되는 반면, 내부적으로 업데이트 할 수 있다면 O (log n). 업데이트를 강제 할 수있는 능력이 좋은 것처럼 보일 것입니다. –
같이 갔던 솔루션을 물어 볼 수 있습니까? 나는 비슷하지만 비슷한 시간에 다른 모든 문제에 대해 ** 모든 항목 **의 우선 순위를 ** 시간에 따라 다시 계산해야합니다 (최소 여유 시간 일정). –