Một heap mềm được định nghĩa là một biến thể trên cấu trúc dữ liệu heap đơn giản bao gồm thời gian phân bổ không đổi cho 5 loại hoạt động. Điều này có được bằng cách cẩn thận "làm hỏng" (tăng) các khóa có tối đa một số giá trị nhất định trong đống. Các hoạt động thời gian không đổi là -
- tạo (các) - Tạo một soft heap mới
- chèn (s, y) - Chèn một phần tử y vào một heap mềm
- meld (s, s ') của hai nhóm mềm s và s ′ thành một, phá hủy cả hai
- xóa (s, y) - Xóa một phần tử y khỏi một heap mềm
- findmin (s) - Nhận phần tử có ít khóa nhất trong soft heap s
- Các đống khác như đống Fibonacci đạt được hầu hết các giới hạn này mà không có bất kỳ sự hỏng hóc nào, nhưng không thể cung cấp giới hạn thời gian cố định đối với thao tác xóa quan trọng. Có thể kiểm soát mức độ hư hỏng bằng cách lựa chọn tham số ε, nhưng giá trị này được đặt càng thấp thì yêu cầu chèn thời gian càng nhiều (O (log 1 / ε) để có tỷ lệ lỗi là ε).
- Chính xác hơn, đảm bảo được cung cấp bởi soft heap là như sau:đối với giá trị cố định ε từ 0 đến 1/2, tại bất kỳ thời điểm nào sẽ có tối đa ε * m khóa bị hỏng trong heap, trong đó m là số lượng phần tử được chèn hoặc bị hỏng W. Chúng tôi không thể đảm bảo rằng chỉ có một tỷ lệ phần trăm cố định trong số các khóa hiện tại trong heap bị hỏng hoặc tăng lên:trong một chuỗi chèn và xóa không mong muốn, có thể xảy ra rằng tất cả các phần tử trong heap sẽ có các khóa tăng lên hoặc bị hỏng. Trong trường hợp tương tự, không có gì đảm bảo rằng trong một chuỗi các phần tử được trích xuất từ đống với findmin và xóa, chỉ một tỷ lệ phần trăm cố định mới có các khóa bị hỏng hoặc tăng lên:trong một trường hợp không may mắn, chỉ các phần tử bị hỏng hoặc tăng lên mới được trích xuất từ heap.
- Mặc dù có những hạn chế và tính chất không thể đoán trước, các soft heap rất hữu ích cho việc thiết kế các Thuật toán xác định. Chúng được thực hiện để có được độ phức tạp tốt nhất cho đến nay để xác định cây khung tối thiểu. Chúng cũng có thể được triển khai để chỉ cần xây dựng một Thuật toán lựa chọn tối ưu và Thuật toán sắp xếp gần, là những Thuật toán đặt mọi phần tử gần vị trí cuối cùng của nó, một tình huống mà việc sắp xếp chèn diễn ra nhanh chóng.