우선 순위 큐에 삽입하는 복잡성

Question

우선 순위 큐에서 처음 두 요소를 팝하고 추가 한 다음 합계를 우선 순위 큐에 다시 삽입하는 다음 코드를 고려하십시오.

while (pq.size() > 1) 
{ 
    // Extract shortest two ropes from pq 
    int first = pq.top(); 
    pq.pop(); 
    int second = pq.top(); 
    pq.pop(); 

    // Connect the ropes: update result and 
    // insert the new rope to pq 
    res += first + second; 
    pq.push(first + second); 
} 

n 요소에 대한 우선 순위 큐에 삽입하는 것이 O (nlogn) 연산임을 알 수 있습니다. 그러나 우선 순위 큐가 배열로 구현된다고 말할 수 있습니다. O (N * N) 연산이되지 않습니까? 또는 n 요소에 대해 위 코드의 복잡성은 어떻게됩니까?

Answer 1

잘 구현 된 우선 순위 대기열은 삽입 당 O (로그 n) 상각 단계에 요소를 삽입합니다. 잘 구현 된 우선 순위 큐는 힙 배열 알고리즘에 따라 배열 요소가 배열 된 배열을 사용할 가능성이 큽니다.