2

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.

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?

Mayur Kulkarni
  • 1,306
  • 10
  • 28
  • Interesting question, but the [Computer Science Stack Exchange](http://cs.stackexchange.com) might be a better forum for it. I might even suggest the a mod should migrate it; someone in that community will probably be able to provide a high quality answer. – Jared Goguen Mar 25 '16 at 05:25
  • 1
    The thing is that you have to maintain your hash map, which also takes O(logn) because you may need to change that many elements' position. – HenryLee Mar 25 '16 at 08:20
  • @HenryLee can you point me to some references where it's proven that a single update might trigger logarithm number of updates? Because I don't seem to find it – Mayur Kulkarni Mar 25 '16 at 09:09
  • Hi @MayurKulkarni. I suppose when the key[w] happens to be in the bottom of the heap, and the updated value is the smallest number, then you need to change O(logn) positions in your heap and as well as the number of updates in hash map. – HenryLee Mar 26 '16 at 05:26
  • @HenryLee Ah, you mean, a single deletion might trigger log number of updates ? (In the HashMap) – Mayur Kulkarni Mar 27 '16 at 14:47
  • No, that's not what I meant. I mean in step 3, you need to do O(logn) changes in the heap, given that if your heap is an array based implementation. Then it will result in O(logn) changes in the hash map. So far I am still assuming one deletion in the hash map costs O(1) operations. – HenryLee Mar 27 '16 at 16:09

1 Answers1

1

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.

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.

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]

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.

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.

Community
  • 1
  • 1
ilim
  • 4,477
  • 7
  • 27
  • 46