0
$\begingroup$

I am planning to use heap structure to find the minimum distance between a set of 2D points and form a cluster.. and after to spend a couple of hours surfing on the internet, I have not still gotten a clearly example.

Imagine you have a set of 2d points (x1,y1; x2,y2;....;xn,yn) and then you compute all possible distances between these pairs of points to finally get a matrix with all distances values.

After that, I want to use a min heap structure to sort data and match the pairs with the mininum distance... and here is my question...

Which value/data is really stored at every root or leaves in heap structure? I know that the root of min Heap is the shortest distance but, the data stored in every globe at Heap graph represent the index of every distances of the pairs of points or the pairs of points?

In the first case, if you store the index value located at the top of heap, Do you need to perform after a new search in the distance matrix to obtain which pairs of points form these shortest distance? Is it optimal to do that?

I hope my question was clear and thanks for your support.

$\endgroup$
0
$\begingroup$

You would put triplets into your heap, storing

(distance, i, j)

where distance is the distance, i and j are the indices.

When you "pop" the topmost (smallest distance) element from the heap using the appropriate algorithm, the second smallest will now become the top.

Python has a module heapq for building min-heaps. Simply add tuples with heapq.heappush, and remove the smallest with heapq.heappop. To convert an array into a heap, use heapq.heapify (faster than calling heappush for every element).

Note that putting n^2 values into a heap yields runtime O(n^2 log n^2) which is fairly expensive.

$\endgroup$
  • $\begingroup$ That's sound a good solution .. do you have a good information how to put triplets into the heap? $\endgroup$ – Camilo Romero Dec 2 '16 at 15:26
  • $\begingroup$ With add... use a heap that stores objects. $\endgroup$ – Anony-Mousse Dec 2 '16 at 22:46
  • $\begingroup$ I am not very familiar with heap. I have just seen few examples on the internet and some operations and It is quite comprehensible. When you mention triplete, I imagined a unique heap with three features that can be ordered to min to max according to one of them and just after that I could extract the min value with indexes that correspond the min distance between 2 pair of points... is that ok?? but I still do not know how to create a heap with triplete array.... thanks for your help $\endgroup$ – Camilo Romero Dec 2 '16 at 23:33
  • $\begingroup$ Python has built-in library functions for this. $\endgroup$ – Anony-Mousse Dec 3 '16 at 21:54
  • $\begingroup$ Do you know what it is? $\endgroup$ – Camilo Romero Dec 3 '16 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.