우선순위 큐를 완벽하게 사용하기 위해 페어링 힙이 구현됩니다. 우선 순위 대기열은 개체 집합의 최소값을 추적하므로 대기열에서 제거할 항목을 가져올 때마다 항상 최소값입니다. 우선 순위 대기열은 대부분 Dijkstra의 알고리즘을 사용하여 그래프에서 최단 경로를 계산할 때 구현됩니다.
페어링 힙은 사용하기 쉽고 실제 애플리케이션에서 잘 작동하기 때문에 완벽합니다. 특히, 그들은 상각 시간에 탁월하게 작동합니다. 개별 작업이 더 오랜 시간을 소비하는 반면 대기열의 전체 수명 주기에 대한 모든 작업의 합은 빠릅니다. 페어링 힙은 코딩하기 쉽고 종종 피보나치 힙보다 더 잘 작동합니다.
페어링 힙에는 매우 간단한 속성이 있습니다. 각 힙은 개체 또는 값과 연결됩니다. 각 힙에는 하위 힙 세트도 있습니다. 개체의 값은 항상 자식 힙의 값보다 크거나 작습니다.
힙에는 몇 가지 기본 작업이 있습니다 -
최소(힙) – 최소값을 가져옵니다. 이 기능은 매우 쉽습니다. 힙의 최상위 값으로 보입니다.
병합(힙1, 힙2) – 두 개의 힙을 병합하거나 결합합니다. 최대값을 가진 힙을 다른 힙의 자식에 추가합니다. 또한 이 기능은 빠릅니다.