Giới thiệu về Soft Heap
Một soft heap là một biến thể của cấu trúc dữ liệu heap đơn giản, cung cấp thời gian trung bình hằng số (constant amortized time) cho 5 loại thao tác. Điều này đạt được bằng cách "phân hủy" (tăng giá trị) khóa của tối đa một số lượng nhất định các phần tử trong heap một cách cẩn thận. Các thao tác thời gian hằng số bao gồm:
- create(s) – Tạo một soft heap mới s
- insert(s, y) – Chèn phần tử y vào soft heap s
- meld(s, s') – Gộp hai soft heap s và s' thành một, hủy cả hai heap gốc
- delete(s, y) – Xóa phần tử y khỏi soft heap s
- findmin(s) – Lấy phần tử có khóa nhỏ nhất trong soft heap s
Các heap khác như Fibonacci heap đạt được hầu hết các giới hạn này mà không cần phân hủy, nhưng không thể cung cấp giới hạn thời gian hằng số cho thao tác xóa quan trọng. Mức độ phân hủy có thể kiểm soát bằng tham số ε, nhưng giá trị ε càng thấp thì thời gian chèn càng lớn (O(log 1/ε) cho tỷ lệ lỗi ε).
Đảm bảo chính xác của Soft Heap
Cụ thể hơn, soft heap đảm bảo: với một giá trị ε cố định giữa 0 và 1/2, tại bất kỳ thời điểm nào, tối đa ε·m khóa bị phân hủy trong heap, trong đó m là số phần tử đã chèn hoặc đã bị phân hủy. Chúng ta không thể đảm bảo rằng chỉ một tỷ lệ cố định các khóa hiện tại trong heap bị phân hủy: trong một chuỗi chèn/xóa không mong muốn, tất cả phần tử trong heap có thể có khóa bị tăng. Tương tự, không có đảm bảo rằng trong chuỗi phần tử trích xuất bằng findmin và delete, chỉ một tỷ lệ cố định có khóa bị phân hủy: trong kịch bản xui xẻo, chỉ các phần tử bị phân huy được trích xuất.
Ứng dụng của Soft Heap
Mặc dù có hạn chế và tính chất khó dự đoán, soft heap hữu ích trong thiết kế thuật toán xác định (deterministic algorithms). Chúng được triển khai để đạt độ phức tạp tốt nhất đến nay cho bài toán cây khung nhỏ nhất (minimum spanning tree). Soft heap cũng có thể dùng để xây dựng thuật toán chọn tối ưu (optimal selection algorithm) và thuật toán sắp xếp gần đúng (near-sorting algorithms) – các thuật toán đưa mọi phần tử gần vị trí cuối cùng, nơi sắp xếp chèn (insertion sort) chạy nhanh.