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.
What is stored in heap structure in the following example?
machine learning;data mining;clustering;algorithms;clusters
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.