피보나치 힙이 계단식 절단이 필요한 이유는 무엇입니까?

Question

'알고리즘 소개'에서 f-heap을 배우고 있으며 '감소 키'작업으로 인해 실제로 혼란 스럽습니다. 왜 이것이 '계단식 절단'이 필요한가?

이 작업이 제거 된 경우 :

는 메이크업 힙(),() 삽입, 최소()와 노동 조합()의 비용이 확실히 변경되지

추출 분()

은 여전히 ​​O O (n (H)) 'consolidate'연산에서 대부분의 뿌리가 낀 나무의 비용은 루트 목록에 추가되었을 때 을 지불 할 수 있고 나머지 비용 O (D (n) n))
1. 감소 키() : 분명히 O (1)

D (n)에 대해서는 정확하게 설명 할 수는 없지만 O (lgn), '계단식 절단'이없는 사촌, 노드 은 조금 나중에 루트 목록으로 이동할 수 있습니다 어떤 노드 은 그의 아버지 아래에 숨기더라도 효율성에 영향을주지 않습니다. 적어도 이것은 상황을 악화시키지 않을 것입니다. 불쌍한 내 영어 :(

이

누군가가 도와 드릴까요? 감사

Answer 1

계단식 인하 이유는 D (n)를 낮게 유지하는 것입니다 위해

죄송합니다. 그것은 밝혀 당신은 임의의 수를 허용하는 경우 노드가 트리에서자를 수 있다면 D (n)은 선형으로 커질 수 있기 때문에 delete와 delete-min은 선형 시간이 걸리게됩니다.

직관적으로, 순서 k의 트리에있는 노드의 수를 지수 적으로 k. 이렇게하면 통합 된 힙에서 대수적으로 많은 트리 만 가질 수 있습니다. 임의의 수의 노드를자를 수 있으면 나무에서, 당신은이 보장을 잃는다. 특히, 주문 k의 나무를 가져다가 손주를 모두자를 수 있습니다. 이것은 k 개의 아이들을 가진 나무를 남기고, 각각은 나뭇잎이다. 결과적으로 k + 1 개의 총 노드 만있는 순서 k의 트리를 만들 수 있습니다. 즉, 최악의 경우 D (n)이 O (log n)가 아닌 n - 1이되도록 모든 노드를 보유하려면 n - 1 차수의 트리가 필요합니다.

희망이 도움이됩니다.