Các thao tác trên Meldable Priority Queue (Hàng đợi ưu tiên có thể gộp)

Tổng quan

Randomized meldable heap (còn gọi Meldable Priority Queue) hỗ trợ các thao tác phổ biến: chèn (insertion), xóa (deletion), và tìm kiếm (findMin). Thao tác chèn và xóa được triển khai dựa trên thao tác đặc thù của meldable heap: Meld(A1, A2).

Meld (Gộp)

Mục tiêu cơ bản của thao tác meld (còn gọi merge) là lấy hai heap (bằng cách lấy nút gốc của từng heap), A1 và A2, gộp chúng, trả về một nút heap đơn lẻ làm kết quả. Nút heap này là gốc của heap chứa tất cả phần tử từ hai cây con gốc tại A1 và A2.

Đặc điểm xuất sắc của meld là có thể định nghĩa đệ quy. Nếu một trong hai heap là null, merge hoàn tất với tập rỗng và trả về gốc của heap không rỗng. Nếu cả A1 và A2 không nil, kiểm tra nếu A1 > A2 thì hoán đổi. Do đó đảm bảo A1 < A2 và nút gốc của heap gộp sẽ chứa A1. Sau đó đệ quy gộp A2 với A1.left hoặc A1.right. Bước này là nơi ngẫu nhiên xuất hiện: quyết định phía nào để gộp được quyết định bằng tung đồng xu.

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

Insert (Chèn)

Với meld hoàn tất, chèn vào meldable heap rất đơn giản. Tạo nút mới a chứa giá trị p. Nút mới này sau đó gộp với gốc heap.

function Insert(p)
Node a = new Node
a.p = p
root = Meld(a, root)
root.parent = nil
increment node count

Remove (Xóa)

Tương tự chèn, Remove() dùng Meld để loại bỏ nút gốc khỏi heap. Thực hiện bằng cách gộp hai con của nút gốc và làm nút trả về thành gốc mới.

function Remove()
rootNode = Meld(rootNode.left, rootNode.right)
if rootNode is not nil => rootNode.parent = nil
decrement node count

FindMin (Tìm nhỏ nhất)

Thao tác đơn giản nhất cho randomized meldable heap, FindMin() chỉ trả về phần tử hiện tại lưu trong nút gốc của heap.

Các thao tác bổ sung

Một số thao tác bổ sung cho meldable heap cũng có hiệu suất O(log n) trường hợp xấu:

Remove(a) – Xóa nút a và khóa của nó khỏi heap.
Absorb(P) – Gộp tất cả phần tử của meldable heap P vào heap này, làm rỗng P.
DecreaseKey(a, q) – Giảm khóa trong nút a xuống q (điều kiện: q ≤ a.p).