Sum*_*Tea 2 algorithm heapsort fibonacci-heap
在教自己的Fibonacci Heap时我有这个问题,现在我知道这是一种有效的数据结构,可以O(1)在降低堆中元素的优先级时实现具有分摊时间复杂度的优先级队列.然而,根据CLRS教科书,优先级降低操作假定节点保持目标元素是预先知道的.我很好奇如果不是最小节点,我怎么能有效地获得所需的节点.一个简单的实现和分析会产生O(n)最坏情况下的时间复杂度,以便在Fibonacci堆上执行查找操作,与其他操作相比效率较低.所以我的问题是在Fibonacci Heap中有一个有效的查找操作,还是有必要的？
首先要说的是:这个结构被设计成一个有效的优先级队列,而不是搜索结构,所以查找操作就是这样O(n).通常,您知道要更改的确切节点.让我们看一个例子 - Dijkstra的算法.
在每个步骤中,您将图形顶点推送到堆或更改其优先级,因此在顶点中保持指向堆节点的指针是很自然的.这样它很棒!
所以基本上你会将指针存储到某个节点(你可以将它们存储在一个hashmap或AVL树中).