소프트 힙(Soft Heap)이란?
소프트 힙(soft heap)은 기본적인 힙(heap) 자료구조의 변형으로, 5가지 핵심 연산을 상수 분할 상환 시간(amortized constant time)에 처리할 수 있는 자료구조입니다. 이러한 성능은 힙에 저장된 값들 중 일정 개수 이하의 키(key)를 신중하게 '오염(corrupting)'시키는 방식, 즉 키 값을 인위적으로 증가시키는 대가를 치르면서 얻어집니다.
상수 시간에 처리되는 연산
소프트 힙에서 상수 시간에 수행되는 연산은 다음과 같습니다.
- create(s) − 새로운 소프트 힙 s를 생성합니다.
- insert(s, y) − 소프트 힙 s에 원소 y를 삽입합니다.
- meld(s, s') − 두 소프트 힙 s와 s'를 하나로 병합하며, 이 과정에서 두 힙은 모두 소멸됩니다.
- delete(s, y) − 소프트 힙 s에서 원소 y를 삭제합니다.
- findmin(s) − 소프트 힙 s에서 가장 작은 키를 가진 원소를 조회합니다.
다른 힙과의 비교
피보나치 힙(Fibonacci heap)과 같은 다른 종류의 힙은 오염 없이도 위 연산 대부분에 대해 동일한 성능 한계를 달성하지만, 가장 중요한 delete 연산에 대해서는 상수 시간 보장을 제공하지 못한다는 한계가 있습니다.
오염 정도 조절: ε 매개변수
키의 오염 정도는 매개변수 ε(엡실론)의 선택을 통해 조절할 수 있습니다. 다만 ε을 낮게 설정할수록 삽입 연산에 더 많은 시간이 소요되며, 오류율 ε에 대해 삽입 연산의 시간 복잡도는 O(log 1/ε)가 됩니다.
소프트 힙이 제공하는 보장
좀 더 정확히 말하면, 소프트 힙의 보장은 다음과 같습니다. 0과 1/2 사이의 고정된 값 ε에 대해, 임의의 시점에서 힙 내 오염된 키의 개수는 최대 ε×m개입니다. 여기서 m은 지금까지 삽입되었거나 오염된 원소의 총 개수입니다.
단, 두 가지 주의할 점이 있습니다. 첫째, 현재 힙에 남아 있는 키 중에서만 일정 비율이 오염되었다고는 보장할 수 없습니다. 삽입과 삭제가 특정 패턴으로 반복되면, 힙에 남아 있는 모든 원소의 키가 증가하거나 오염될 수 있습니다. 둘째, findmin과 delete를 통해 힙에서 추출되는 원소들 역시 일정 비율만 오염되었다고 보장할 수 없으며, 운이 나쁜 경우 오염된 원소들만 연달아 추출될 가능성도 있습니다.
소프트 힙의 활용
이러한 한계와 예측하기 어려운 특성에도 불구하고, 소프트 힙은 결정론적(deterministic) 알고리즘 설계에서 강력한 도구로 활용됩니다. 소프트 힙은 2000년 버나드 샤젤(Bernard Chazelle)이 고안했으며, 이를 활용해 당시까지 가장 우수한 시간 복잡도를 기록한 최소 신장 트리(minimum spanning tree) 알고리즘이 개발되었습니다. 또한 최적의 선택(selection) 알고리즘을 간단하게 구현하거나, 근사 정렬(near-sorting) 알고리즘을 만드는 데에도 사용됩니다. 근사 정렬은 모든 원소를 최종 위치 근처까지만 배치하는 방식으로, 이렇게 되면 삽입 정렬(insertion sort)이 매우 빠르게 동작한다는 점을 이용합니다.