무작위 혼합 가능 힙(Meldable Priority Queue라고도 함)은 여러 공통 작업을 지원합니다. 이를 삽입, 삭제 및 검색 작업인 findMin이라고 합니다. 삽입 및 삭제 작업은 혼합 가능한 힙 Meld(A1, A2)에 고유한 추가 작업 측면에서 구현됩니다.
혼합
병합(병합이라고도 함) 작업의 기본 목표는 두 개의 힙(각 힙 루트 노드를 가져옴) A1과 A2를 가져와 병합하여 결과적으로 단일 힙 노드를 반환하는 것입니다. 이 힙 노드는 A1과 A2에 뿌리를 둔 두 하위 트리의 모든 요소를 포함하는 힙의 루트 노드입니다.
이 혼합 연산의 뛰어난 특징은 재귀적으로 정의할 수 있다는 것입니다. 힙 중 하나가 null 값과 연결된 경우 병합은 빈 집합으로 수행되고 메서드는 비어 있지 않은 힙의 루트 노드를 반환합니다. A1과 A2가 모두 nil이 아니면 A1> A2인지 확인하십시오. 그렇다면 두 개를 바꿉니다. 따라서 A1
혼합 작업이 완료되면 혼합 가능한 힙에 삽입하는 것이 매우 간단합니다. 먼저 값 p를 포함하는 새 노드 a가 생성됩니다. 이 새 노드는 단순히 힙 루트 노드와 병합됩니다.
삽입 작업과 마찬가지로 Remove()는 Meld 작업을 구현하여 힙에서 루트 노드를 제거합니다. 이것은 단순히 루트 노드의 두 자식을 병합하고 반환된 노드를 새 루트로 만드는 것으로 수행됩니다.
무작위 혼합 가능 힙에 대한 가장 간단한 작업인 FindMin()은 단순히 힙의 루트 노드에 저장된 현재 요소를 반환합니다.
추가 작업
O(logn) 최악의 경우 효율성이 있는 혼합 가능한 힙에 적용할 수 있는 몇 가지 추가 작업은 다음과 같습니다. -function Meld(Node A1, Node A2)
if A1 is nil => return A2
if A2 is nil => return A1
if A1 > A2 => swap A1 and A2
if coin_toss is 0 => A1.left = Meld(A1.left, A2)
else A1.right = Meld(A1.right, A2)
return A1
삽입
function Insert(p)
Node a = new Node
a.p = p
root = Meld(a, root)
root.parent = nil
increment node count
제거
function Remove()
rootNode = Meld(rootNode.left, rootNode.right)
if rootNode is not nil => rootNode.parent = nil
decrement node count
최소 찾기