소프트 힙

Soft heap
캔터베리 씬 밴드는 소프트 힙을 참조하십시오.

컴퓨터 과학에서 소프트 힙은 단순 힙 데이터 구조에서 변형된 것으로, 5가지 유형의 운영에 대해 상각된 시간 복잡성이 지속적으로 존재한다.이는 힙에서 최대 일정 수의 값의 키를 조심스럽게 "파손"(증가)함으로써 달성된다.일정한 시간 연산은 다음과 같다.

  • 생성(S): 새 소프트 힙 생성
  • 삽입(S, x): 부드러운 힙에 요소 삽입
  • meld(S, S'): 두 개의 부드러운 힙의 내용물을 하나로 결합하여 둘 다 파괴한다.
  • 삭제(S, x): 소프트 힙에서 요소 삭제
  • findmin(S): 소프트 힙에 최소 키가 있는 요소 가져오기

피보나치 힙스와 같은 다른 힙은 이 한계치의 대부분을 아무런 부패 없이 달성하지만, 중요한 삭제 작업에 대해 일정한 시간 제한을 제공할 수는 없다.부패의 양은 파라미터 ε의 선택에 의해 조절할 수 있지만, 이 값이 낮을수록 삽입에 더 많은 시간이 필요하다(오류율 rate에 대한 O(로그 1/ 1)).

더 정확히 말하면, 소프트 힙이 제공하는 보증은 다음과 같다: 0과 1/2 사이의 고정값 for에 대해, 어느 시점이라도 힙에 ε*n의 손상 키가 있을 것이다. 여기서 n은 지금까지 삽입된 요소의 수입니다.이는 현재 힙에 있는 키의 고정 비율만 손상된다는 것을 보장하지는 않는다는 점에 유의하십시오. 삽입 및 삭제의 불운한 순서로 힙의 모든 요소가 손상된 키를 가질 수 있다는 점에 유의하십시오.마찬가지로, 우리는 지뢰와 함께 힙에서 추출된 요소들의 시퀀스에서는 고정된 백분율만이 손상된 키를 가질 것이라는 보장이 없다: 불길한 시나리오에서는 손상된 요소들만 힙에서 추출된다.

부드러운 힙은 2000년에 버나드 샤젤에 의해 디자인되었다.이 구조에서 '부패'라는 용어는 차젤이 부드러운 무더기 속에서 '카풀링'이라고 부른 결과물이다.소프트 힙의 각 노드에는 링크된 키 목록과 하나의 공통 키가 포함되어 있다.공통 키는 링크된 목록의 키 값에 대한 상한이다.일단 키가 링크된 목록에 추가되면, 그 값은 소프트 힙 작업에서 다시는 관련되지 않기 때문에 손상된 것으로 간주된다. 즉, 공통 키만 비교된다.이것이 부드러운 힙을 "부드럽게" 만드는 것이다; 당신은 그것에 투입된 어떤 특정한 가치가 손상될 것인지 아닌지 확신할 수 없다.이러한 부패의 목적은 효과적으로 데이터의 정보 엔트로피를 낮추어 데이터 구조가 힙에 관한 정보-이론적 장벽을 돌파할 수 있게 하는 것이다.

적용들

이러한 한계와 예측 불가능한 특성에도 불구하고 소프트 힙은 결정론적 알고리즘 설계에 유용하다.그것들은 최소 스패닝 트리를 찾기 위해 지금까지 최고의 복잡성을 얻기 위해 사용되었다.또한 삽입 정렬이 빠른 상황에서 모든 요소를 최종 위치에 가깝게 배치하는 알고리즘인 니어 정렬 알고리즘뿐만 아니라 최적의 선택 알고리즘을 쉽게 구축하는 데도 사용할 수 있다.

가장 간단한 예 중 하나는 선택 알고리즘이다.n개의 숫자 그룹 중 k번째를 찾고 싶다고 말해봐.첫째, 오류율 1/3을 선택한다. 즉, 삽입한 키의 약 33%가 손상될 것이다.이제 힙에 모든 n개의 요소를 삽입한다. 즉, 원래 값을 "올바른" 키라고 하고, 힙에 저장된 값을 "저장된" 키라고 부른다.이때, 대부분의 n/3 키가 손상된다. 즉, n/3 키는 "올바른" 키보다 큰 "저장된" 키가 되며, 다른 모든 키의 경우 저장된 키는 올바른 키와 같다.

다음으로 힙에서 최소 요소를 3번 삭제한다(이 작업은 "저장된" 키에 따라 수행됨).지금까지 우리가 한 총 삽입 횟수가 여전히 n회이기 때문에, 힙에는 여전히 1/3의 손상 키가 있다.따라서 힙에 남아 있는 키 중 적어도 2n/3 - n/3 = n/3은 손상되지 않는다.

L은 우리가 제거한 원소들 중에서 가장 큰 정확한 키를 가진 원소가 되게 하라.L의 저장된 키는 올바른 키보다 클 수 있으며(L이 손상된 경우), 이 큰 값조차도 힙에 있는 나머지 요소의 모든 저장된 키보다 작다(최소값을 제거할 때).따라서 L의 정확한 키는 소프트 힙의 나머지 n/3 비파손 요소보다 작다.따라서 L은 원소를 33%/66%와 66%/33%로 나눈다.그런 다음 파티션 알고리즘을 사용하여 L에 대한 세트를 퀵소트로부터 분할하고 L보다 작은 숫자 집합 또는 L보다 큰 숫자 집합에 동일한 알고리즘을 다시 적용하며, 둘 중 어느 것도 2n/3 요소를 초과할 수 없다.각 삽입과 삭제에는 O(1) 상각 시간이 필요하므로 총 결정론적 시간은 T(n) = T(2n/3) + O(n)이다.분할 및 재무 재발을 위한 마스터 정리의 사례 3(ε=1 및 c=2/3)을 사용하여, 우리는 T(n) = n(n)을 알고 있다.

최종 알고리즘은 다음과 같다.

기능이 부드럽다힙선택(a[1n], k) k = 1이면 최소(a[1n]) create(S)를 1에서 n/3 x := findmin(S, x) xIndex := 파티션(a, x) // 부드러운 경우 피벗 x의 새 인덱스 반환힙 선택(a[1..)xIndex-1], k) 기타 소프트힙 선택(a[xIndex..n], k-xIndex+1)

참조

  • Chazelle, Bernard (November 2000). "The soft heap: an approximate priority queue with optimal error rate" (PDF). J. ACM. 47 (6): 1012–1027. CiteSeerX 10.1.1.5.9705. doi:10.1145/355541.355554.
  • Kaplan, Haim; Zwick, Uri (2009). "A simpler implementation and analysis of Chazelle's soft heaps". Proceedings of the Nineteenth Annual ACM–SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. pp. 477–485. CiteSeerX 10.1.1.215.6250. doi:10.1137/1.9781611973068.53. ISBN 978-0-89871-680-1.