19. Fibonacci Heaps

피보나치 힙은 병합 가능한 힙의 기능과 분할 상환 상수 시간의 연산 동작을 제공한다.

Mergeable heaps

병합 가능한 힙은 다음의 5가지 연산을 지원한다.

MAKE-HEAP()은 힙을 만든다. \Theta(1).

INSERT(H, x)은 원소 x를 삽입한다. \Theta(1).

MINIMUM(H)은 최소값을 리턴한다. \Theta(1).

EXTRACT-MIN(H)는 최소값을 삭제한 뒤 추출해 반환한다. O(\lg n).

UNION(H_1, H_2)는 H_1과 H_2를 병합한 새 힙을 생성한다. \Theta(1).

피보나치 힙은 여기에 추가로 2개의 연산을 더 지원한다.

DECREASE-KEY(H, x, k)는 x의 키를 현재 키 이하인 k로 감소시킨다. \Theta(1).

DELETE(H, x)는 원소 x를 삭제한다. O(\lg n).

피보나치 힙은 DECREASE-KEY와 UNION이 많이 일어날 때 좋다. 아니라면 별로 유용하지 않다.

19.1. Structure of Fibonacci heaps

피보나치 힙최소 힙 순서화된 트리들의 모임이다. 각 트리는 최소 힙 특성을 따른다. 각 노드는 부모에 대한 포인터와 자식들 중 하나에 대한 포인터를 갖고 있다. 자식들은 이중 순환 연결 리스트인 자식 리스트를 구성한다. 노드들은 자식의 수와, 그 노드가 마지막으로 다른 노드의 자식이 된 후에 자식을 잃었는지를 체크하는 mark를 특성으로 갖는다. 피보나치 힙의 경우 최소값을 포함하는 트리의 루트에 대한 포인터를 최소 노드로 갖는다. 트리들의 루트는 이중 연결 리스트인 루트 리스트를 형성한다. 피보나치 힙은 전체 원소 수도 특성으로 갖는다.

Potential function

피보나치 힙의 잠재 함수 \Phi(H) = t(H) + 2m(H)로 정의된다. (t(H)는 루트 리스트의 트리 수, m(H)는 마크된 노드의 수)

Maximum degree

노드의 최대 차수 D(n) = O(\lg n)이다.

19.2. Mergable-heap operations

병합 가능한 힙의 여러 연산들은 서로 성능에 트레이드오프 관계가 있다.

Creating a new Fibonacci heap

MAKE-FIB-HEAP은 빈 피보나치 힙을 만들며, O(1)이다.

Inserting a node

노드 삽입은 다음과 같다.

FIB-HEAP-INSERT(H, x)
x.degree = 0
x.p = NIL
x.child = NIL
x.mark = FALSE
if H.min == NIL
    create a root list for H containing just x
    H.min = x
else
    insert x into H's root list
    if x.key < H.min.key
        H.min = x
H.n++

수행 시간은 O(1)이다.

Finding the minimum node

최소 노드를 찾는 것은 O(1)이다.

Uniting two Fibonacci heaps

두 피보나치 힙을 병합하는 것은 다음과 같으며, O(1)이다.

FIB-HEAP-UNION(H_1, H_2)
H = MAKE-FIB-HEAP()
H.min = H_1.min
concatenate the root list of H_2 with the root list of H
if (H_1.min == NIL) or (H_2.min ≠ NIL and H_2.min.key < H_1.min.key)
    H.min = H_2.min
H.n = H_1.n + H_2.n
return H

Extracting the minimum node

피보나치 힙에서 최소 원소를 빼내는 것은 다음과 같으며, O(lg n)이다.

FIB-HEAP-EXTRACT-MIN(H)
z = H.min
if z ≠ NIL
    for each child x of z
        add x to the root list of H
        x.p = NIL
    remove z from the root list of H
    if z == z.right
        H.min = NIL
    else
        H.min = z.right
        CONSOLIDATE(H)
    H.n--
return z
CONSOLIDATE(H)
Let A[0, ..., D(H.n)] be a new array
for i = 0 to D(H.n)
    A[i] = NIL
for each node w in the root list of H
    x = w
    d = x.degree
    while A[d] ≠ NIL
        y = A[d]
        if x.key > y.key
            swap(x, y)
        FIB-HEAP-LINK(H, y, x)
        A[d] = NIL
        d++
    A{d] = x
H.min = NIL
for i = 0 to D(H.n)
    if A[i] ≠ NIL
        if H.min == NIL
            create a root list for H containing just A[i]
            H.min = A[i]
        else
            insert A[i] into H's root list
            if A[i].key < H.min.key
                H.min = A[i]
FIB-HEAP-LINK(H, y, x)
remove y from the root list of H
make y a child of x, incrementing x.degree
y.mark = FALSE

19.3. Decreasing a key and deleting a node

키 감소는 분할 상환 O(1)이고, 노드 삭제는 분할 상환 O(D(n))이다.

Decreasing a key

키 감소는 다음과 같다.

FIB-HEAP-DECREASE-KEY(H, x, k)
if k > x.key
    error "new key is greater than current key"
x.key = k
y = x.p
if y ≠ NIL and x.key < y.key
    CUT(H, x, y)
    CASCADING-CUT(H, y)
if x.key < H.min.key
    H.min = x
CUT(H, x, y)
remove x from the child list of y, decrementing y.degree
add x to the root list of H
x.p = NIL
x.mark = FALSE
CASCADING-CUT(H, y)
z = y.p
if z ≠ NIL
    if y.mark == FALSE
        y.mark = TRUE
    else 
        CUT(H, y, z)
        CASCADING-CUT(H, z)

Deleting a node

노드 삭제는 다음과 같다. O(lg n)이다.

FIB-HEAP-DELETE(H, x)
FIB-HEAP-DECREASE-KEY(H, x, -∞)
FIB-HEAP-EXTRACT-MIN(H)

19.4. Bounding the maximum degree

다음 정리가 성립한다.

Lemma. 피보나치 힙 내의 노드 x에 대해 해당 노드의 차수가 k라 하자. y_{1}, \cdots, y_{k}를 x에 연결된 순서대로 x의 자식들을 나열한 것이라 했을 때, y_{1}의 차수는 0 이상이며 i \geq 2에 대해 y_{i}의 차수는 i – 2 이상이다.

Lemma. 피보나치 수 F_{k}에 대해, F_{k + 2} = 1 + \sum_{i=0}^{k} F_{i}이다.

Lemma. 피보나치 수 F_{k+2} \geq \phi^{k}이다.

Lemma. 피보나치 힙 내의 노드 x에 대해, x.size \geq F_{k+2} \geq \phi^{k}이다.

Corollary. 노드 n개 피보나치 힙의 노드의 최대 차수는 O(\lg n)이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중