랜덤화 혼합 가능 힙
Randomized meldable heap컴퓨터 과학에서 랜덤화 멜더블 힙(Meldable Heap 또는 Randomized Meldable Priority Queue)은 기본 구조가 힙 순서 바이너리 트리인 priority 큐 기반의 데이터 구조입니다.그러나 기본 이진 트리의 모양에는 제한이 없습니다.
이 접근법에는 유사한 데이터 구조보다 많은 이점이 있습니다.또한 단순성이 향상되어 랜덤화된 혼합형 힙의 모든 작업을 쉽게 구현할 수 있으며 복잡도 경계의 상수 요인이 작습니다.또, 밸런스 조건을 유지할 필요도 없고, 노드내의 위성 정보도 필요 없습니다.마지막으로, 이 구조는 최악의 경우 시간 효율이 우수합니다.각 개별 연산의 실행 시간은 기껏해야 높은 [1]확률로 로그가 됩니다.
운용
랜덤화된 멜더블히프는 많은 공통 작업을 지원합니다.삽입, 삭제 및 검색 조작인 findMin 입니다.삽입 및 삭제 조작은 멜드 힙(Q1, Q2)에 고유한 추가 조작의 관점에서 구현됩니다.
멜드
meld(마지라고도 함) 작업의 기본 목표는 (각 힙 루트 노드를 취함으로써) Q1과 Q2의 2개의 힙을 취하여 병합하고 결과적으로 단일 힙 노드를 반환하는 것입니다.이 히프 노드는 Q1과 Q2에 루트된2개의 서브트리의 모든 요소를 포함하는 히프의 루트노드입니다
이 meld 연산의 장점은 재귀적으로 정의할 수 있다는 것입니다.어느 하나의 힙이 null인 경우 병합은 빈 집합과 함께 수행되며 메서드는 단순히 비어 있지 않은 힙의 루트 노드를 반환합니다.Q1과 Q2가 모두 0이 아닌 경우 Q1 > Q2인지 확인합니다.문제가 있는 경우는, 2개를 교환합니다.따라서 Q1 < Q2 및 Marge된 힙의 루트노드에 Q1이 포함되어 있는 것을 확인합니다.다음으로 Q2를 Q1.left 또는 Q1.right와 재귀적으로 Marge합니다.이 단계에서 어느 쪽과 병합할지는 동전 던지기에 의해 결정되므로 랜덤화가 이루어집니다.
Q1이 0인 경우 Meld(노드 Q1, 노드 Q2)는 Q2가 0인 경우 Q2를 반환합니다.Q1 > Q2 => 스왑 Q1 및 Q2가 0 = > Q1 왼쪽 = Meld(노드 Q1 왼쪽, 노드 Q2 오른쪽)입니다.
삽입
meld 작업이 완료되면 meldable 힙에 쉽게 삽입할 수 있습니다.먼저 값 x를 포함하는 새로운 노드 u를 작성한다.이 새로운 노드는 힙 루트 노드와 간단히 혼합됩니다.
함수 삽입(x) 노드 u = 새 노드 u.x = x 루트 = Meld(u, root) root.parent = 0 증분 노드 수
제거한다.
마찬가지로 삽입 조작도 간단합니다.Remove()는 Meld 조작을 사용하여 루트노드를 힙에서 삭제합니다.이것은 루트 노드의 두 아이를 혼합하여 반환된 노드를 새 루트로 만드는 것만으로 이루어집니다.
제거() 루트 = Meld(root.left, root.right) (루트가 영이 아닌 경우) => root.parent = 영의 감소 노드 수
최소 검색
랜덤화된 멜더블히프에 대해 가장 쉬운 조작인 FindMin()은 힙의 루트 노드에 현재 저장되어 있는 요소를 단순히 반환합니다.
추가 작업
O(logn) Worst-case 효율도 갖는 혼합 가능한 힙에 대해 구현할 수 있는 몇 가지 추가 작업은 다음과 같습니다.
- Remove(u) - 노드 u 및 해당 키를 힙에서 제거합니다.
- 흡수(Q) - 혼합 가능한 힙 Q의 모든 요소를 이 힙에 추가하고 프로세스에서 Q를 비웁니다.
- DecrementKey(u, y) - 노드 u의 키를 y로 줄입니다(사전 조건: y <= u.x).
효율성 분석
모든 비정수 시간 연산은 멜드 연산의 관점에서 정의되므로, 이러한 연산의 효율성은 두 개의 랜덤화된 힙을 혼합하는 복잡성 분석을 통해 결정할 수 있습니다.
이 분석의 결과 n노드의 랜덤화된 힙에서 혼합 가능한 priority 큐 동작의 예상 시간은 O(logn)[1][2]입니다.
| 작동 | 최악의 경우 시간 효율 |
|---|---|
| 멜드(Q1, Q2) | O(로그인) |
| 삽입(x) | O(로그인) |
| 삭제() | O(로그인) |
| Find Min() | O(1) |
| 삭제(x) | O(로그인) |
| 흡수(Q) | O(로그인) |
역사
멜더블 힙은 1998년 감빈과 말리노스키에 [1]의해 처음 제안된 것으로 보인다.
변종
랜덤화 멜더블히프는 멜더블히프 구현의 가장 단순한 형태이지만 다른 형태도 존재합니다.다음과 같습니다.
