혼합 가능한 우선 순위 대기열 및 스큐 힙

통합 가능한 우선 순위 대기열

정의

무작위 혼합 가능 힙(또한 혼합 가능 힙 또는 무작위 혼합 가능 우선 순위 대기열)은 기본 구조도 힙 순서 이진 트리인 우선 순위 대기열 기반 데이터 구조로 정의됩니다. 그러나 기본 이진 트리의 모양에 대한 엄격하고 빠른 규칙은 없습니다.

장점

• 이 접근 방식은 유사한 데이터 구조에 비해 여러 가지 장점이 있습니다.
• 다른 데이터 구조보다 간단한 접근 방식을 제공합니다.
• 무작위 혼합 가능 힙에 대한 모든 작업은 적용하기 쉽고 복잡도 경계의 상수 요소가 작습니다.
• 또한 균형 상태를 유지할 필요가 없으며 노드 내 위성 정보가 필요하지 않습니다.
• 마지막으로, 이 구조는 최악의 경우 시간 효율성이 좋습니다. 대부분 각 개별 작업의 실행 시간은 높은 확률로 대수입니다.

힙 기울이기

스큐 힙(또는 자체 조정 힙)은 이진 트리로 구현된 힙 데이터 구조로 정의됩니다.

스큐 힙은 바이너리 힙보다 더 빨리 병합할 수 있기 때문에 유리합니다.

바이너리 힙과 달리 구조적 제약이 없으므로 트리의 높이가 대수라는 보장이 없습니다.

두 가지 조건만 충족해야 합니다 -

• 일반 힙 순서가 유지되어야 하지만(루트는 최소값이고 하위 트리에 대해 재귀적으로 동일함) 균형 속성(마지막을 제외한 모든 수준은 가득 차 있어야 함)은 필요하지 않습니다.
• 스큐 힙의 주요 작업은 병합뿐입니다. Merge와 관련된 insert, extractMin() 등과 같은 다른 작업만 구현할 수 있습니다.

예시

스큐 힙 1이 되도록

가정할 두 번째 힙

그리고 우리는

재귀적 병합 프로세스

merge(a1, a2) a1과 a2를 병합할 두 개의 최소 스큐 힙이라고 하자. a1의 루트를 a2의 루트보다 작게 둡니다(더 작지 않은 경우 교환하여 동일한 값을 얻을 수 있습니다). a1->left와 a1->right.a1->left =merge(a2, a1->left)