소프트 힙은 5가지 유형의 작업에 대해 일정한 상각 시간으로 구성된 단순 힙 데이터 구조의 변형으로 정의됩니다. 이것은 힙에서 최대 특정 수의 키를 신중하게 "손상"(증가)하여 얻습니다. 일정한 시간 연산은 -
- 만들기 − 새로운 소프트 힙 생성
- 삽입(들, y) − 요소 y를 소프트 힙 s에 삽입
- 혼합(s, s') 두 개의 소프트 힙 및 s'를 하나로 통합하여 둘 다 파괴
- 삭제(s, y) − 소프트 힙 s에서 요소 y 삭제
- 찾기 − 소프트 힙에서 키가 가장 적은 요소 가져오기
- 피보나치 힙과 같은 다른 힙은 손상 없이 이러한 경계의 대부분을 달성하지만 중요한 삭제 작업에 일정한 시간 경계를 제공할 수는 없습니다. 손상 정도는 매개변수 ε을 선택하여 제어할 수 있지만 이 값이 낮을수록 삽입에 더 많은 시간이 필요합니다(ε의 오류율에 대해 O(log 1/ε)).
- 더 정확하게 말하면, 소프트 힙이 제공하는 보장은 다음과 같습니다. 0과 1/2 사이의 고정 값 ε에 대해 어느 시점에서든 힙에 최대 ε*m개의 손상된 키가 있습니다. 여기서 m은 삽입되거나 손상된 요소의 수 W. 현재 고정된 비율의 키만 보장할 수는 없습니다. 힙에서 손상되거나 증가됨:원치 않는 삽입 및 삭제 시퀀스에서 힙의 모든 요소가 증가하거나 손상된 키를 가질 수 있습니다. 같은 경우 findmin을 사용하여 힙에서 추출된 요소 시퀀스에서 삭제하고 고정된 비율만 키가 손상되거나 증가합니다. 불행한 시나리오에서는 손상되거나 증가한 요소만 힙에서 추출됩니다.
- 소프트 힙은 한계와 예측할 수 없는 특성에도 불구하고 결정론적 알고리즘을 설계하는 데 유용합니다. 최소 스패닝 트리를 결정하기 위해 현재까지 최고의 복잡성을 얻기 위해 구현되었습니다. 또한 삽입 정렬이 빠른 상황에서 모든 요소를 최종 위치에 가깝게 설정하는 알고리즘인 최적 선택 알고리즘과 근접 정렬 알고리즘을 간단히 구축하도록 구현할 수도 있습니다.