우선 순위 대기열에서 자체 정렬을 다시 수행하려면 어떻게해야합니까?

Question

직원 목록을 추적하는 우선 순위 대기열이 있으며 처음에 정렬하기 위해 사용하는 비교기가 현재 "Invite Value"로 정렬합니다. 그래서 최대 초대 값 Employee를 선택하고 초대 한 다음 다음 최대 초대 값 직원을 다시 선택하겠습니다. 까다로운 부분은 특정 직원을 초대 한 후 목록에있는 다른 직원의 초대 값에 영향을 미친다는 것입니다. 나는 그것이 가치가 invValueChanged 필드의보고 초대 마지막을 기준으로 다시 계산 될 필요가 있다면 다음

PriorityQueue<Employee> leafs = new PriorityQueue<>(); 
//populating the queue happens here 

while(!leafs.isEmpty()){ 

Employee maxLeaf = leafs.peek(); 
     int maxValue = maxLeaf.getInviteValue(); 

     maxLeaf.invite(); 
     totalValue += maxValue; 
     k--; 

     for(Employee e : leafs){ 
      if(e.invValueChanged){ 
       leafs.remove(e); 
       leafs.add(e); 
      } 
     } 
} 

각 직원이 알 시도했습니다. 이 코드는 우선 순위 대기열에 오류가 발생했습니다.

Answer 1

여기서 문제는 데이터 구조의 다른 요소를 변경해야한다는 것입니다.

요소를 반복하고 조작 할 수는 없으므로 요소의 순서가 변경됩니다.

이 작업을 수행하는 가장 좋은 방법은 현재 구조의 벡터를 만들고 벡터에서 연산을 수행 한 다음 다시 삽입하는 것입니다.

속도가 문제가되는 경우이 작업은 작성한 코드와 동일한 시간 복잡성을 갖습니다.

우선 순위 큐에 요소를 삽입하면 O (log (n)) 시간이 걸립니다. 그러면 n 번 수행되므로 O (n log (n)) 시간이됩니다.

priory 큐에서 벡터를 만들려면 O (n) 시간이 필요합니다. 우선 순위 큐의 모든 요소를 ​​벡터로부터 삽입하면 O (n log (n)) 시간이 걸립니다.

따라서 속도는 점근 적으로 동일해야합니다. 실제 속도 또한 매우 근접해야합니다.