在Prim算法中保持不变 [英] Maintaining invariant in Prim's Algorithm

问题描述

算法2"中的Tim Roughgarden讲授了以下方法来更新min堆中的相邻顶点(从堆中提取min后):

Tim Roughgarden in Algorithms 2 course teaches the following approach for updating the adjacent vertices in the min heap (after extracting min from the heap):

When a vertice v is added to the MST:
  For each edge (v,w) in the unexplored tree:
      1. Delete w from the min heap.
      2. Recompute the key[w] (i.e. it's value from the unexplored tree
         to the explored one).
      3. Add the value back to the heap.

因此，基本上，这涉及从堆中删除(以及需要O(logn)的heapify)，然后重新插入(再次是O(logn))

So, basically this involves deletion from the heap (and heapify which takes O(logn)) and then reinserting (again O(logn))

相反，如果我使用以下方法:

Instead, if I use the following approach:

For each edge (v,w) in the unexplored tree:
    1. Get the position of the node in the heap(array) using HashMap -> O(1)
    2. Update the value in place.
    3. Bubble up or bubble down accordingly. -> O(logn)

尽管它们在渐近性上相同，但后者给出了更好的常数.那么它比课程中的那个更好吗?还是我错过了什么?

Although they're the same asymptotically, the latter one gives better constants. So is it better than the one in the course? Or am I missing something?

推荐答案

它在渐近上是相同的，您将有较高的概率获得更好的常数.您尝试使用HashMap实现的目标使用了 O(n)额外的空间.另外，在最坏的情况下，它需要 O(logn)的额外时间，与删除操作相同从堆将花费.但是，它花时间与logn成正比的概率确实很低.您可以查看要使用的特定HashMap实现的概率性能分析.如果您有兴趣了解更多有关此的信息.

It is asymptotically the same, and you would get a better constant factor with a high probability. What you try to achieve with HashMap uses O(n) extra space. Also, in worst case, it takes O(logn) extra time, same as a remove from heap would cost. However, its probability of taking time proportional to logn is really low. You may look into a probabilistic performance analysis of particular HashMap implementation you intend to use. if you're interested in figuring out more about that.

我可以提出一种更好的解决方案，避免使用HashMap，因此由于不需要概率分析，因此更易于观察/分析常数因子.

I could propose a better solution that avoids usage of HashMap, and is consequently easier to observe/analyze constant factor due not not requiring probabilistic analysis.

解决方案是将键值存储在外部数组A中，并重写堆的比较函数，以便它根据存储在A中的对应值比较堆中的元素.

The solution is storing the key values in an external array A and overriding the comparison function of the heap so that it compares the elements inside it based on their corresponding values which are stored in A.

换句话说，许多堆实现中的默认比较函数如下.

In other words, the default comparison function in many heap implementations are as follows.

function compare(a, b):
    return a < b

在更新时，您将其更改为:

While updating it, you will change it to:

function compare(a, b):
    return A[a] < A[b]

在数组A中，每个顶点v将具有一个对应的像元，从而导致 O(n)额外的空间使用情况，就像您的HashMap想法一样.但是，即使在最坏的情况下，将v添加到发现的节点上来更新该值也将花费 O(1)时间.

In array A, each vertex v will have a corresponding cell, causing O(n) extra space usage, just like your HashMap idea. But updating that value upon adding v to discovered nodes will take O(1) time even in the worst case.

可能无法基于您在其中实现的编程语言以及用于堆的库进行此更新，但是可以以多种语言和语言进行，包括但不限于C ++的STL的std :: priority_queue.如果您要尝试使用这样的自定义数据结构，则也可以使用自定义的堆实现来实现.

It may not be possible to make this update based on the programming language you implement in and libraries you use for heap, but it is possible in many languages and languages including and not limited to C++'s std::priority_queue of STL. You may implement this with a custom implementation of heap as well, if experimenting with such a custom data structure is what you're after.

这篇关于在Prim算法中保持不变的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！