1.9.3 std::priority_queue

우선순위 큐(priority queue)는 힙(heap)이라고 부르는 매우 유용한 구조를 제공합니다. 힙은 컨테이너에서 가장 작은(또는 가장 큰) 원소에 빠르게 접근할 수 있는 자료 구조입니다. 최소/최대 원소에 접근하는 동작은 O(1)의 시간 복잡도를 가집니다. 원소 삽입은 O(log n) 시간 복잡도로 동작하며, 원소 제거는 최소/최대 원소에 대해서만 가능합니다.

여기서 유의해야 할 점은 최대 또는 최소 둘 중 하나에 대해서만 적용할 수 있으며, 최대와 최소에 한꺼번에 빠르게 접근할 수는 없습니다. 최대와 최소 중 어느 것에 빠르게 접근할 것인지는 컨테이너 비교자에 의해 결정됩니다. std::stack이나 std::queue와는 달리 std::priority_queue는 기본적으로 std::vector를 기본 컨테이너로 사용하며, 필요한 경우 변경할 수 있습니다. 비교자는 기본적으로 std::less를 사용합니다. 그러므로 기본적으로는 최대 힙(max heap)으로 생성되며, 이는 최대 원소가 맨 위에 나타나게 됨을 의미합니다.

새로운 원소를 삽입할 때마다 최대 또는 최소 원소가 최상위에 위치하도록 설정해야 하기 때문에 단순하게 기본 컨테이너 함수를 호출하는 형태로 동작할 수 없습니다. 대신 비교자를 사용하여 최대 또는 최소 데이터를 맨 위까지 끌어올리는 히피파이(heapify) 알고리즘을 구현해야 합니다. 이러한 연산은 컨테이너 크기에 대한 로그 형태의 시간을 소요하며, O(log n) 시간 복잡도로 표현합니다. 여러 개의 원소를 이용하여 우선순위 큐를 초기화할 때에도 이러한 작업이 수행됩니다. 그러나 std::priority_queue 생성자는 단순히 초기화 원소에 대해 각각 삽입 함수를 호출하지 않습니다. 대신 O(n) 시간 복잡도로 빠르게 동작하는 다른 힙 생성 알고리즘을 사용합니다.