피보나치 힙 데이터 구조의 직관은 무엇입니까?

피보나치 힙 데이터 구조의 직관은 무엇입니까?

---

Fibonacci 힙에 대한 Wikipedia 기사를 읽고 CLRS의 데이터 구조에 대한 설명을 읽었지만이 데이터 구조가 작동하는 이유에 대한 직관을 거의 제공하지 않습니다. 피보나치 힙이있는 그대로 디자인 된 이유는 무엇입니까? 어떻게 작동합니까?

감사!

---

이 답변은 꽤 길겠지만 피보나치 힙의 출처에 대한 통찰력을 제공하는 데 도움이되기를 바랍니다. 저는 여러분이 이미 이항 힙 과 상각 분석에 익숙하다고 가정하겠습니다 .

동기 부여 : 왜 피보나치가 힙을 사용 하는가?

피보나치 힙에 뛰어 들기 전에 애초에 왜 그것들이 필요한지 알아 보는 것이 좋을 것입니다. 다른 유형의 힙 (예 : 이진 힙 및 이항 힙) 이 많이 있는데, 다른 힙이 필요한 이유는 무엇입니까?

주된 이유는 Dijkstra의 알고리즘 과 Prim의 알고리즘에 있습니다. 이러한 그래프 알고리즘은 모두 관련 우선 순위가있는 노드를 보유하는 우선 순위 대기열을 유지하여 작동합니다. 흥미롭게도 이러한 알고리즘은 감소 키라 는 힙 작업에 의존합니다.이미 우선 순위 대기열에있는 항목을 가져온 다음 키를 줄입니다 (즉, 우선 순위를 높임). 실제로 이러한 알고리즘의 많은 런타임은 감소 키를 호출해야하는 횟수로 설명됩니다. 감소 키를 최적화하는 데이터 구조를 구축 할 수 있다면 이러한 알고리즘의 성능을 최적화 할 수 있습니다. 이진 힙 및 이항 힙의 경우 감소 키에는 시간 O (log n)가 소요됩니다. 여기서 n은 우선 순위 큐의 노드 수입니다. 그것을 O (1)로 떨어 뜨릴 수 있다면, Dijkstra의 알고리즘과 Prim의 알고리즘의 시간 복잡도는 O (m log n)에서 (m + n log n)으로 떨어질 것입니다. 이는 이전보다 점근 적으로 더 빠릅니다. 따라서 감소 키를 효율적으로 지원하는 데이터 구조를 구축하는 것이 좋습니다.

더 나은 힙 구조 설계를 고려해야하는 또 다른 이유가 있습니다. 빈 바이너리 힙에 요소를 추가 할 때 각 삽입에는 시간 O (log n)가 걸립니다. n 개의 요소를 모두 미리 알고 있으면 시간 O (n)에서 바이너리 힙 을 빌드 할 수 있지만 요소가 스트림에 도착하면 불가능합니다. 이항 힙의 경우 n 개의 연속 요소를 삽입하는 것은 각각 분할 된 시간 O (1)이 걸리지 만 삽입이 삭제와 인터레이스되면 삽입에 각각 Ω (log n) 시간이 걸릴 수 있습니다. 따라서 삽입을 최적화하는 우선 순위 큐 구현을 검색하여 각각 시간이 O (1) 걸릴 수 있습니다.

1 단계 : 게으른 이항 힙

피보나치 힙 빌드를 시작하기 위해 이항 힙으로 시작하여 삽입에 시간이 걸리도록 수정합니다. O (1). 이것을 시도하는 것은 그다지 불합리한 것이 아닙니다. 결국 우리가 많은 삽입을 수행하고 많은 디큐를 수행하지 않으려면 삽입을 최적화하는 것이 합리적입니다.

기억 하시겠지만, 이항 힙은 힙의 모든 요소를 이항 트리 모음에 저장하는 방식으로 작동합니다 . n 차 이항 트리에는 ^{2n 개의} 노드가 있으며 힙은 모두 힙 속성을 따르는 이항 트리 모음 인 구조입니다. 일반적으로 이항 힙의 삽입 알고리즘은 다음과 같이 작동합니다.

• 새로운 싱글 톤 노드를 생성합니다 (이것은 차수 0의 트리입니다).
• 순서 0의 트리가있는 경우 :
  • 순서 0의 두 트리를 함께 순서 1의 트리로 병합합니다.
  • 순서 1의 트리가있는 경우 :
    • 순서 1의 두 트리를 함께 트리 순서 2로 병합합니다.
    • 2 차 트리가있는 경우 :
    • ...

이 프로세스는 각 시점에서 각 주문에 대해 최대 하나의 트리가 있는지 확인합니다. 각 트리는 순서보다 기하 급수적으로 더 많은 노드를 보유하기 때문에 총 트리 수가 적어 대기열에서 빼기가 빠르게 실행됩니다 (대기열에서 빼기 최소 단계를 수행 한 후 너무 많은 다른 트리를 볼 필요가 없기 때문에).

그러나 이것은 또한 노드를 이항 힙에 삽입하는 최악의 런타임이 Θ (log n)임을 의미합니다. 함께 병합해야하는 Θ (log n) 트리가있을 수 있기 때문입니다. 이러한 트리는 대기열에서 빼기 단계를 수행 할 때 트리 수를 낮게 유지해야하기 때문에 함께 병합되어야하며, 향후 삽입시 트리 수를 낮게 유지하는 데 아무런 이점이 없습니다.

이것은 이항 힙에서 첫 번째 출발을 소개합니다.

수정 1 : 힙에 노드를 삽입 할 때 순서 0의 트리를 생성하여 기존 트리 컬렉션에 추가하면됩니다. 트리를 함께 통합하지 마십시오.

우리가 할 수있는 또 다른 변화가 있습니다. 일반적으로 두 개의 이항 힙을 병합 할 때 결과 트리에 각 순서의 트리가 많아야 하나가되도록 병합 단계를 수행하여 이들을 결합합니다. 다시 말하지만, 우리는 대기열에서 빼기가 빠르도록이 압축을 수행하며, 병합 작업이이 비용을 지불해야하는 실제 이유가 없습니다. 따라서 두 번째 변경을 수행합니다.

수정 2 : 두 힙을 병합 할 때 병합을 수행하지 않고 모든 트리를 함께 결합합니다. 나무를 함께 통합하지 마십시오.

이 변경을 수행하면 대기열에 추가 작업에서 O (1) 성능을 매우 쉽게 얻을 수 있습니다. 새 노드를 만들고 트리 컬렉션에 추가하는 것뿐입니다. 그러나 이렇게 변경하고 다른 작업을 수행하지 않으면 대기열에서 빼기 작업의 성능이 완전히 중단됩니다. dequeue-min은 가장 작은 값을 찾을 수 있도록 최소값을 제거한 후 힙에있는 모든 트리의 루트를 스캔해야합니다. Θ (n) 노드를 삽입하여 추가하면 대기열에서 빼기 작업은 이러한 모든 트리를 살펴 보는 데 Θ (n) 시간을 소비해야합니다. 엄청난 성능 저하입니다 ... 피할 수 있을까요?

삽입이 실제로 더 많은 트리를 추가하는 경우 첫 번째 대기열에서 제거하는 데 확실히 Ω (n) 시간이 걸립니다. 그러나 그렇다고 모든 대기열에서 빼는 데 비용이 많이 드는 것은 아닙니다 . 대기열에서 빼기를 수행 한 후 힙의 모든 트리를 결합하여 각 주문의 트리가 하나만 생성되도록하면 어떻게됩니까? 처음에는 시간이 오래 걸리지 만, 연속해서 여러 개의 대기열에서 빼기 시작하면 주변에 나무가 더 적어지기 때문에 향후 대기열에서 빼기가 훨씬 빨라질 것입니다.

하지만이 설정에는 약간의 문제가 있습니다. 일반 이항 힙에서 트리는 항상 순서대로 저장됩니다. 새 나무를 계속해서 나무 모음에 던지고 무작위 시간에 병합하고 그 이후에 더 많은 나무를 추가한다면 나무가 어떤 순서로든 될 것이라는 보장은 없습니다. 따라서 우리는 이러한 트리를 병합하는 새로운 알고리즘이 필요합니다.

이 알고리즘의 직관은 다음과 같습니다. 트리 순서에서 트리로 매핑되는 해시 테이블을 생성한다고 가정합니다. 그런 다음 데이터 구조의 각 트리에 대해 다음 작업을 수행 할 수 있습니다.

• 해당 주문의 트리가 이미 있는지 찾아보십시오.
• 그렇지 않은 경우 현재 트리를 해시 테이블에 삽입합니다.
• 그렇지 않으면:
  • 현재 트리를 해당 순서의 트리와 병합하여 해시 테이블에서 이전 트리를 제거합니다.
  • 이 과정을 재귀 적으로 반복하십시오.

이 작업은 완료되면 각 주문에 대해 최대 하나의 트리가 있음을 보장합니다. 또한 상대적으로 효율적입니다. T 개의 총 트리로 시작하여 총 t 개의 트리로 끝났다고 가정합니다. 우리가 할 총 병합 횟수는 T-t-1이 될 것이며, 병합을 할 때마다 O (1) 시간이 걸립니다. 따라서이 작업의 런타임은 트리 수 (각 트리가 한 번 이상 방문 됨)와 수행 된 병합 수에서 선형이됩니다.

트리 수가 적 으면 (예 : Θ (log n)),이 작업은 시간 O (log n) 만 걸립니다. 트리 수가 많으면 (예 : Θ (n)),이 작업은 Θ (n) 시간이 걸리지 만 Θ (log n) 트리 만 남게되므로 향후 대기열에서 훨씬 더 빠르게 대기열을 빼낼 수 있습니다.

상각 분석을 수행하고 잠재적 인 함수를 사용하여 얼마나 더 나은 결과를 얻을 수 있는지 정량화 할 수 있습니다. Φ를 우리의 잠재적 인 함수로, Φ를 데이터 구조의 트리 수로합시다. 즉, 운영 비용은 다음과 같습니다.

• 삽입 : O (1)이 작동하고 잠재력을 1 씩 증가시킵니다. 상각 후원가는 O (1)입니다.
• 병합 : O (1)이 작동합니까? 한 힙의 잠재력은 0으로 떨어지고 다른 힙의 잠재력은 상응하는 양만큼 증가하므로 잠재력에는 순 변화가 없습니다. 따라서 상각 된 비용은 O (1)입니다.
• Dequeue-Min : O (#trees + #merges)가 작동하고 잠재력을 Θ (log n), 즉 우리가 트리를 열심히 병합한다면 이항 트리에있을 수있는 트리 수로 감소시킵니다. 우리는 이것을 다른 방식으로 설명 할 수 있습니다. 나무의 수를 Θ (log n) + E로 작성합시다. 여기서 E는 "초과"나무의 수입니다. 이 경우 수행 된 총 작업은 Θ (log n + E + #merges)입니다. 초과 트리 당 하나의 병합을 수행하므로 총 작업은 Θ (log n + E)입니다. 우리의 잠재력은 나무의 수를 Θ (log n) + E에서 Θ (log n)까지 떨어 뜨리기 때문에 전위의 감소는 -E입니다. 따라서 dequeue-min의 상각 된 비용은 Θ (log n)입니다.

dequeue-min의 상각 된 비용이 Θ (log n) 인 이유를 확인하는 또 다른 직관적 인 방법 은 잉여 트리가있는 이유를 확인하는 것입니다. 이 여분의 나무는 욕심 많은 삽입물이 여분의 나무를 모두 만들고 비용을 지불하지 않기 때문에 존재합니다! 따라서 우리는 모든 병합을 수행하는 것과 관련된 비용을 그 시간을 모두 차지한 개별 삽입으로 되돌릴 수 있으며, Θ (log n) "핵심"작업과 우리가 비난 할 다른 작업을 남겨 둘 수 있습니다. 삽입.

따라서:

수정 3 : 대기열에서 빼기 작업에서 모든 트리를 통합하여 각 주문에 대해 최대 하나의 트리가 있도록합니다.

이 시점에서 삽입 및 병합은 O (1) 시간에 실행되고 dequeue는 상각 시간 O (log n)에 실행됩니다. 꽤 멋져요! 그러나 아직 감소 키가 작동하지 않습니다. 그것은 도전적인 부분이 될 것입니다.

2 단계 : 감소 키 구현

지금은 피보나치 힙이 아닌 "지연 이항 힙"이 있습니다. 이항 힙과 피보나치 힙 사이의 실제 변화는 우리가 감소 키를 구현하는 방법입니다.

키 감소 작업은 힙에 이미있는 항목 (일반적으로 포인터가 있음)과 기존 우선 순위보다 낮은 새 우선 순위를 가져야합니다. 그런 다음 해당 요소의 우선 순위를 새롭고 낮은 우선 순위로 변경합니다.

간단한 알고리즘을 사용하여이 작업을 매우 빠르게 (시간 O (log n)) 구현할 수 있습니다. 키를 줄여야하는 요소 (O (1) 시간에 위치 할 수 있습니다. 포인터가 있다고 가정하고 있음을 기억하십시오)하고 우선 순위를 낮 춥니 다. 그런 다음 우선 순위가 상위 노드보다 낮은 한 상위 노드와 반복적으로 스왑하고 노드가 휴식을 취하거나 트리의 루트에 도달하면 중지합니다. 이 작업은 각 트리의 높이가 최대 O (log n)이고 각 비교에는 시간 O (1)이 걸리기 때문에 시간 O (log n)가 걸립니다.

그러나 우리는 이것보다 더 나은 것을 시도하고 있다는 것을 기억하십시오-우리는 런타임이 O (1)이되기를 원합니다! 그것은 일치 하기 매우 어려운 바운드입니다. 우리는 노드를 트리 위나 아래로 이동시키는 어떤 프로세스도 사용할 수 없습니다. 그 트리는 Ω (log n) 일 수있는 높이를 가지고 있기 때문입니다. 좀 더 과감한 것을 시도해야합니다.

노드의 키를 줄이고 싶다고 가정 해 보겠습니다. 힙 속성이 위반되는 유일한 방법은 노드의 새 우선 순위가 상위 항목보다 낮은 경우입니다. 특정 노드에 뿌리를 둔 하위 트리를 보면 여전히 힙 속성을 따릅니다. 그래서 여기 완전히 미친 생각이 있습니다. 노드의 키를 줄일 때마다 부모 노드에 대한 링크를 끊은 다음 노드에 뿌리를 둔 전체 하위 트리를 트리의 최상위 수준으로 다시 가져 오면 어떨까요?

수정 4 : 노드의 키를 줄이게하고 우선 순위가 상위의 우선 순위보다 작 으면 잘라내어 루트 목록에 추가합니다.

이 작업의 효과는 무엇입니까? 몇 가지 일이 일어날 것입니다.

1. 이전에 노드를 자식으로 가졌던 노드는 이제 자식 수가 잘못되었다고 생각합니다. n 차 이항 트리는 n 개의 자식을 갖도록 정의되었지만 더 이상 사실이 아닙니다.
2. 루트 목록의 트리 컬렉션이 증가하여 향후 대기열에서 빼기 작업 비용이 증가합니다.
3. 힙에있는 나무가 더 이상 이항 나무 일 필요는 없습니다. 그들은 다양한 시점에서 아이를 잃은 "이전의"이항 나무 일 수 있습니다.

Number (1) isn't too much of a problem. If we cut a node from its parent, we can just decrease the order of that node by one to indicate that it has fewer children than it thought it previously did. Number (2) also isn't a problem. We can just backcharge the extra work done in the next dequeue-min operation to the decrease-key operation.

Number (3) is a very, very serious issue that we will need to address. Here's the problem: the efficiency of a binomial heap partially stems from the fact that any collection of n nodes can be stored in a collection of Θ(log n) trees of different order. The reason for this is that each binomial tree has 2ⁿ nodes in it. If we can start cutting nodes out of trees, then we risk having trees that have a large number of children (that is, a high order) but which don't have many nodes in them. For example, suppose we start with a single tree of order k and then perform decrease-key operations on all the grandchildren of k. This leaves k as a tree with order k, but which only contains k + 1 total nodes. If we keep repeating this process everywhere, we might end up with a bunch of trees of various orders that have a very small number of children in them. Consequently, when we do our coalesce operation to group the trees together, we might not reduce the number of trees to a manageable level, breaking the Θ(log n)-time bound that we really don't want to lose.

At this point, we're in a bit of a bind. We need to have a lot of flexibility with how the trees can be reshaped so that we can get the O(1) time decrease-key functionality, but we can't let the trees get reshaped arbitrarily or we will end up with decrease-key's amortized runtime increasing to something greater than O(log n).

The insight needed - and, quite honestly, what I think is the real genius in the Fibonacci heap - is a compromise between the two. The idea is the following. If we cut a tree from its parent, we're already planning on decreasing the rank of the parent node by one. The problem really arises when a node loses a lot of children, in which case its rank decreases significantly without any nodes higher up in the tree knowing about it. Therefore, we will say that each node is only allowed to lose one child. If a node loses a second child, then we'll cut that node from its parent, which propagates the information that nodes are missing higher up in the tree.

It turns out that this is a great compromise. It lets us do decrease-keys quickly in most contexts (as long as the nodes aren't children of the same tree), and only rarely do we have to "propagate" a decrease-key by cutting a node from its parent and then cutting that node from its grandparent.

To keep track of which nodes have lost children, we'll assign a "mark" bit to each node. Each node will initial have the mark bit cleared, but whenever it loses a child it will have the bit set. If it loses a second child after the bit has already been set, we'll clear the bit, then cut the node from its parent.

Modification 5: Assign a mark bit to each node that is initially false. When a child is cut from an unmarked parent, mark the parent. When a child is cut from a marked parent, unmark the parent and cut the parent from its parent.

In this older Stack Overflow question, I've sketched out a proof that shows that if trees are allowed to be modified in this way, then any tree of order n must contain at least Θ(φⁿ) nodes, where φ is the golden ratio, about 1.61. This means that the number of nodes in each tree is still exponential in the order of the tree, though it's a lower exponent from before. As a result, the analysis we did earlier about the time complexity of the decrease-key operation still holds, though the term hidden in the Θ(log n) bit will be different.

There's one very last thing to consider - what about the complexity of decrease-key? Previously, it was O(1) because we just cut the tree rooted at the appropriate node and moved it to the root list. However, now we might have to do a "cascading cut," in which we cut a node from its parent, then cut that node from its parent, etc. How does that give O(1) time decrease-keys?

The observation here is that we can add a "charge" to each decrease-key operation that we can then spend to cut the parent node from its parent. Since we only cut a node from its parent if it's already lost two children, we can pretend that each decrease-key operation pays for the work necessary to cut its parent node. When we do cut the parent, we can charge the cost of doing so back to one of the earlier decrease-key operations. Consequently, even though any individual decrease-key operation might take a long time to finish, we can always amortize the work across the earlier calls so that the runtime is amortized O(1).

Step Three: Linked Lists Abound!

There is one final detail we have to talk about. The data structure I've described so far is tricky, but it doesn't seem catastrophically complicated. Fibonacci heaps have a reputation for being fearsome... why is that?

The reason is that in order to implement all of the operations described above, the tree structures need to be implemented in very clever ways.

Typically, you'd represent a multiway tree either by having each parent point down to all the children (perhaps by having an array of children) or by using the left-child/right-sibling representation, where the parent has a pointer to one child, which in turn points to a list of the other children. For a binomial heap, this is perfect. The main operation we need to do on trees is a join operation in which we make one root node a child of another, so it's perfectly reasonable to the pointers in the tree directed from parents to children.

The problem in a Fibonacci heap is that this representation is inefficient when considering the decrease-key step. Fibonacci heaps need to support all the basic pointer manipulations of a standard binomial heap and the ability to cut a single child from a parent.

Consider the standard representations of multiway trees. If we represent the tree by having each parent node store an array or list of pointers to its children, then we can't efficiently (in O(1)) remove a child node from the list of children. In other words, the runtime for decrease-key would be dominated by the bookkeeping step of removing the child rather than the logical step of moving a subtree to the root list! The same issue appears in the left-child, right-sibling representation.

The solution to this problem is to store the tree in a bizarre fashion. Each parent node stores a pointer to a single (and arbitrary) one of its children. The children are then stored in a circularly-linked list, and each points back up to its parent. Since it's possible to concatenate two circularly-linked lists in O(1) time and to insert or remove a single entry from one in O(1) time, this makes it possible to efficiently support the necessary tree operations:

• Make one tree a child of another: if the first tree has no children, set its child pointer to point to the second tree. Otherwise, splice the second tree into the circularly-linked child list of the first tree.

• Remove a child from a tree: splice that child node out of the linked list of children for the parent node. If it's the single node chosen to represent the children of the parent node, choose one of the sibling nodes to replace it (or set the pointer to null if it's the last child.)

There are absurdly many cases to consider and check when performing all these operations simply due to the number of different edge cases that can arise. The overhead associated with all the pointer juggling is one of the reasons why Fibonacci heaps are slower in practice than their asymptotic complexity might suggest (the other big one is the logic for removing the minimum value, which requires an auxiliary data structure).

Modification 6: Use a custom representation of the tree that supports efficient joining of trees and cutting one tree from another.

Conclusion

I hope this answer sheds some light on the mystery that is the Fibonacci heap. I hope that you can see the logical progression from a simpler structure (the binomial heap) to a more complex structure by a series of simple steps based on reasonable insights. It's not unreasonable to want to make insertions amortized-efficient at the expense of deletions, and it's similarly not too crazy to implement decrease-key by cutting out subtrees. From there, the rest of the details are in ensuring that the structure is still efficient, but they're more consequences of the other parts rather than causes.

If you're interested in learning more about Fibonacci heaps, you may want to check out this two-part series of lecture slides. Part one introduces binomial heaps and shows how lazy binomial heaps work. Part two explores Fibonacci heaps. These slides go into more mathematical depth than what I've covered here.

Hope this helps!

참고URL : https://stackoverflow.com/questions/19508526/what-is-the-intuition-behind-the-fibonacci-heap-data-structure