스큐 힙

스큐 힙(또는 자체 조정 힙)은 이진 트리로 구현되는 힙 데이터 구조다.스큐 힙은 바이너리 힙보다 더 빨리 병합할 수 있기 때문에 유리하다.이항 적층과는 대조적으로 구조적인 제약이 없기 때문에 나무의 높이가 로그라는 보장은 없다.다음 두 가지 조건만 충족해야 한다.

일반 힙 순서를 적용해야 함
두 스큐 힙의 모든 작업(추가, 제거_min, 병합)은 특수 스큐 힙 합병을 사용하여 수행해야 한다.

스큐 힙은 두 힙을 병합할 때 병합 경로의 모든 노드를 무조건 스와핑하여 균형을 유지하려는 좌익 힙의 자체 조정 형태다.(값을 추가 및 제거할 때도 병합 연산을 사용한다.)구조적인 제약이 없다면, 꼬치 더미는 끔찍하게 비효율적일 것 같다.그러나 상각된 복잡성 분석을 사용하여 스큐 힙의 모든 작업이 O(log n)에서 수행될 수 있음을 입증할 수 있다.^[1]실제로 황금비를 나타내는 ${\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ ${\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ = 1 ${\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ + 5 ${\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ ${\$ { $1+{\sqrt{5}}{2}}:}}$ 의 경우 정확한 상각 복잡도는 log_φ n(약 1.44 log₂ n)인 것으로 알려져 있다.^[2]^[3]

정의

스큐 힙은 다음과 같은 재귀적 정의로 설명할 수 있다.^{[citation needed]}

요소 하나만 있는 힙은 꼬치 힙이다.
두 $sh_{1}$ 개의 꼬치 $sh_{1}$ s $sh_{1}$ $sh_{1}$ ${\$ 1}와 $sh_{2}$ h $sh_{2}$ ${\$ 2}} $개$ 를 합친 결과도 꼬치 힙이다 $sh_{2}$ .

운영

두 히프 병합

두 개의 꼬치덩어리가 합쳐질 때, 우리는 두 개의 좌익 덩어리 병합과 비슷한 과정을 사용할 수 있다.

두 무더기의 뿌리를 비교해 보아라.p뿌리가 작은 더미가 되고, q가 다른 더미가 된다.내버려두다r결과적인 새로운 힙의 이름이다.
r의 근본을 의 근본으로 삼아라.p(작은 뿌리), 그리고 r의 오른쪽 하위 트리를 p의 왼쪽 하위 트리로 하자.
이제 p의 오른쪽 하위 트리를 q와 재귀적으로 병합하여 r의 왼쪽 하위 트리를 계산한다.

템플릿<계급 T, 계급 CompareFunction> 스큐노드<T>* CSkewHeap<T, CompareFunction>::_Merge(스큐노드<T>* 루트_1, 스큐노드<T>* root_) {     스큐노드<T>* 퍼스트루트 = 루트_1;     스큐노드<T>* 세컨드루트 = root_;      만일 (퍼스트루트 == NULL)         돌아오다 세컨드루트;      다른 만일 (세컨드루트 == NULL)         돌아오다 퍼스트루트;      만일 (sh_suff->덜(퍼스트루트->핵심을, 세컨드루트->핵심을))     {         스큐노드<T>* 템파이프 = 퍼스트루트->우측 노드;         퍼스트루트->우측 노드 = 퍼스트루트->좌노드;         퍼스트루트->좌노드 = _Merge(세컨드루트, 템파이프);         돌아오다 퍼스트루트;     }     다른         돌아오다 _Merge(세컨드루트, 퍼스트루트); }

비재귀 병합

그 대신에, 더 말이 많고 처음부터 약간의 분류가 필요한 비재발적 접근법이 있다.

모든 경로를 절단하여 각 힙을 하위 트리로 분할한다.(루트 노드에서 오른쪽 노드를 절단하고 올바른 하위 트리를 자체 하위 트리로 만드십시오.)이렇게 되면 뿌리가 왼쪽 아이만 낳거나 아예 아이가 없는 나무 세트가 된다.
각 하위 트리의 루트 노드 값을 기준으로 하위 트리를 오름차순으로 정렬하십시오.
아직 여러 개의 하위 트리가 있는 동안, 마지막 두 개의 하위 트리를 반복적으로 재결합한다(오른쪽에서 왼쪽으로).
- 두 번째에서 마지막 하위 트리의 루트에 왼쪽 아이가 있으면 오른쪽 아이로 바꾸십시오.
- 마지막 하위 트리의 루트를 두 번째에서 마지막 하위 트리의 왼쪽 자식과 연결하십시오.

값 추가

스큐 힙에 값을 추가하는 것은 트리를 하나의 노드와 원래 트리와 병합하는 것과 같다.

값 제거

힙의 첫 번째 값은 루트를 제거하고 하위 하위 하위 트리를 병합하여 제거할 수 있다.

실행

많은 기능 언어에서 스큐 힙은 구현이 매우 간단해진다.여기 Haskell에서 완전한 샘플 구현이 있다.

자료 스큐헤프 a = 비어 있음                   노드. a (스큐헤프 a) (스큐헤프 a)  싱글톤 :: 서드 a => a -> 스큐헤프 a 싱글톤 x = 노드. x 비어 있음 비어 있음  결합하다 :: 서드 a => 스큐헤프 a -> 스큐헤프 a -> 스큐헤프 a 비어 있음              `결합하다` t2                 = t2 t1                 `결합하다` 비어 있음              = t1 t1@(노드. x1 l1 r1) `결합하다` t2@(노드. x2 l2 r2)      x1 <= x2                                 = 노드. x1 (t2 `결합하다` r1) l1      그렇지 않으면                                = 노드. x2 (t1 `결합하다` r2) l2  삽입하다 :: 서드 a => a -> 스큐헤프 a -> 스큐헤프 a 삽입하다 x 산더미처럼 쌓다 = 싱글톤 x `결합하다` 산더미처럼 쌓다  추출민 :: 서드 a => 스큐헤프 a -> 어쩌면 (a, 스큐헤프 a) 추출민 비어 있음        = 아무 것도 없어요. 추출민 (노드. x l r) = 그냥 (x, l `결합하다` r)

참조

^ Sleator, Daniel Dominic; Tarjan, Robert Endre (February 1986). "Self-Adjusting Heaps". SIAM Journal on Computing. 15 (1): 52–69. CiteSeerX 10.1.1.93.6678. doi:10.1137/0215004. ISSN 0097-5397.
^ Kaldewaij, Anne; Schoenmakers, Berry (1991). "The Derivation of a Tighter Bound for Top-Down Skew Heaps" (PDF). Information Processing Letters. 37 (5): 265–271. CiteSeerX 10.1.1.56.8717. doi:10.1016/0020-0190(91)90218-7.
^ Schoenmakers, Berry (1997). "A Tight Lower Bound for Top-Down Skew Heaps" (PDF). Information Processing Letters. 61 (5): 279–284. CiteSeerX 10.1.1.47.447. doi:10.1016/S0020-0190(97)00028-8.

외부 링크

[1] Sleator, Daniel Dominic; Tarjan, Robert Endre (February 1986). "Self-Adjusting Heaps". SIAM Journal on Computing. 15 (1): 52–69. CiteSeerX 10.1.1.93.6678. doi:10.1137/0215004. ISSN 0097-5397.

[2] Kaldewaij, Anne; Schoenmakers, Berry (1991). "The Derivation of a Tighter Bound for Top-Down Skew Heaps" (PDF). Information Processing Letters. 37 (5): 265–271. CiteSeerX 10.1.1.56.8717. doi:10.1016/0020-0190(91)90218-7.

[3] Schoenmakers, Berry (1997). "A Tight Lower Bound for Top-Down Skew Heaps" (PDF). Information Processing Letters. 61 (5): 279–284. CiteSeerX 10.1.1.47.447. doi:10.1016/S0020-0190(97)00028-8.

[1]

[2]

[3]

Search