如何实现Prim算法与斐波那契堆？ [英] How to implement Prim's algorithm with a Fibonacci heap?
问题描述
我知道 Prim算法，我知道它的实现，但我总是跳过，我现在要问的一部分。有人撰文指出，Prim算法的实现与斐波那契堆是 O（E + V登录（V） ）和我的问题是：
I know Prim's algorithm and I know its implementation but always I skip a part that I want to ask now. It was written that Prim's algorithm implementation with Fibonacci heap is O(E + V log(V)) and my question is:
- 什么是短暂的一个斐波那契堆？
- 它是如何实现的？和
- 您如何实现Prim算法与斐波那契堆？
推荐答案
一个斐波那契堆是一个相当复杂的优先级队列具有优异的amoritzed在其所有业务渐近行为 - 插入，找到分钟，并减少键都跑在O（1）摊销时间，同时删除并提取-分钟运行在摊销O（LG n）的时间。如果你想关于这个问题的一个很好的参考，我强烈建议拿起副本算法导论，第二版，由CLRS和阅读的章节就可以了。这是非常精心编写的，很能说明问题。 的斐波那契堆的原始论文弗里德曼和的Tarjan 可用在网上，你可能要检查出来。这是密集的，但给出了一个很好的治疗材料。
A Fibonacci heap is a fairly complex priority queue that has excellent amoritzed asymptotic behavior on all its operations - insertion, find-min, and decrease-key all run in O(1) amortized time, while delete and extract-min run in amortized O(lg n) time. If you want a good reference on the subject, I strongly recommend picking up a copy of "Introduction to Algorithms, 2nd Edition" by CLRS and reading the chapter on it. It's remarkably well-written and very illustrative. The original paper on Fibonacci heaps by Fredman and Tarjan is available online, and you might want to check it out. It's dense, but gives a good treatment of the material.
如果你想看到斐波那契堆和Prim算法的实现，我必须给一个无耻的插头我自己的实现：
If you'd like to see an implementation of Fibonacci heaps and Prim's algorithm, I have to give a shameless plug for my own implementations:
- My implementation of a Fibonacci heap.
- My implementation of Prim's algorithm using a Fibonacci heap.
在这两种实现的意见应提供它的工作方式pretty的很好的说明;让我知道如果有什么我可以做澄清！
The comments in both of these implementations should provide a pretty good description of how they work; let me know if there's anything I can do to clarify!
这篇关于如何实现Prim算法与斐波那契堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
