최대 우선 순위 대기열에서 최소 요소 가져 오기

Question

priority queue에서 최소 요소를 가져 오는 가장 효율적인 방법은 무엇입니까?

일반 priority queue을 생성했다고 가정 해 봅시다. 이제이 queue에는 고양이와 고양이가 들어 있습니다. 고양이가 먹는 물고기의 수를 나타내는 변수가있는 물고기가 있습니다. 가장 적은 물고기를 먹어서 더 많은 물고기를주는 고양이를 얻고 싶습니다. sortpriority queue 다시 나는 swim()를 호출하여 뿌리에 더 가깝게 먹은 물고기를 얻는다.) 그러나 priority queue이 최대 (최대, 최소 일 수는 없음)이기 때문에 어떻게하면 가장 적은 물고기를 먹은 고양이를 얻을 수 있습니까?

Answer 1

최상위 요소가 가장 큰 우선 순위 큐가 주어진다면, 가장 작은 항목을 얻는 유일한 방법은 큐에서 모든 요소를 ​​제거하는 것입니다. 마지막으로 제거한 항목이 가장 작은 항목입니다. 이 접근법의 복잡성은 O (n log n)입니다. 마지막으로 팝업 한 항목을 제거한 후에는 팝업 한 항목을 저장하고 다시 대기열에 넣어야합니다.

우선 순위 큐를 이진 최대 힙으로 구현 한 것처럼 보입니다. 이 경우, 가장 작은 항목은 마지막 n/2 항목에 정의에 의해 잎이됩니다. 따라서 보조 배열에 대한 액세스 권한이있는 경우 가장 작은 항목에 대해 마지막 n/2 항목을 검색 할 수 있습니다. 그것은 O (n) 연산입니다.

가장 작은 항목을 제거하는 것이 정기적으로 수행해야하는 경우 min-max heap을 구현하는 것이 좋습니다.

Answer 2

물고기의 주문 속성을 재정의하십시오.

comparator 개념을 사용하는 언어로 작업하는 경우,이를 수행하는 한 가지 방법은 물고기의 기본 순서 지정 속성을 바꾸는 비교기를 작성하는 것입니다. 또 다른 대안은 고양이를 만들거나 밀 때 생선 수의 음수를 저장하는 것입니다. 논리는 고양이 개체에 내장 될 수 있으므로 사용자는 양의 양의 물고기 만보고 조작하지만 내부적으로는 음수 값으로 저장됩니다.