Heap ngẫu nhiên có thể hàn được (còn được gọi là Hàng đợi ưu tiên có thể hàn) hỗ trợ một số hoạt động phổ biến. Chúng được gọi là chèn, xóa và thao tác tìm kiếm, findMin. Các hoạt động chèn và xóa được thực hiện theo một hoạt động bổ sung cụ thể cho đống có thể hàn, Meld (A1, A2).
Meld
Mục tiêu cơ bản của hoạt động meld (còn được gọi là hợp nhất) là lấy hai heap (bằng cách lấy từng nút gốc của từng heap), A1 và A2 và hợp nhất chúng, kết quả là trả về một nút heap duy nhất. Nút heap này là nút gốc của heap chứa tất cả các phần tử từ hai cây con có gốc tại A1 và A2.
Một tính năng tuyệt vời của hoạt động meld này là nó có thể được định nghĩa một cách đệ quy. Nếu một trong hai heap được liên kết với giá trị null, thì quá trình hợp nhất được thực hiện với một tập hợp trống và phương thức trả về nút gốc của heap không trống. Nếu cả A1 và A2 đều không phải là nil, hãy kiểm tra xem A1> A2. Nếu đúng, hãy hoán đổi cả hai. Do đó, đảm bảo rằng A1
Với thao tác meld hoàn tất, việc chèn vào đống có thể hàn thật đơn giản. Đầu tiên, một nút mới, a, được tạo có chứa giá trị p. Sau đó, nút mới này chỉ được hợp nhất với nút gốc của đống.
Tương tự như thao tác chèn dễ dàng, Remove () thực hiện thao tác Meld để loại bỏ nút gốc khỏi heap. Điều này được thực hiện bằng cách chỉ cần ghép hai nút con của nút gốc và biến nút trả về làm nút gốc mới.
Có thể là hoạt động đơn giản nhất cho heap ngẫu nhiên có thể kết hợp, FindMin () chỉ cần trả về phần tử hiện tại được lưu trữ trong nút gốc của heap.
Hoạt động bổ sung
Một số hoạt động bổ sung có thể được áp dụng cho đống có thể hàn cũng có hiệu quả trong trường hợp xấu nhất là O (logn) là - 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
Chèn
function Insert(p)
Node a = new Node
a.p = p
root = Meld(a, root)
root.parent = nil
increment node count
Xóa
function Remove()
rootNode = Meld(rootNode.left, rootNode.right)
if rootNode is not nil => rootNode.parent = nil
decrement node count
FindMin