Using A Heap Sort To Find The Closest Point

Identifying The Approach

There are several ways that a problem such as this could be solved, I have opted to go with a distance based vector approach. Essentially, let’s say we have our target point at [0,0] and we have another point [7, 6]. It can be represented on a graph like so:

Graph showing [0,0] and [7, 6]
Pythagoras Equation For Distance Vector
let data = [[-2,4], [0,-2], [-1,0], [3,-5], [-2,-3], [3,8]];
[ { points: [ -2, 4 ], distance: 4.47213595499958 },{ points: [ 0, -2 ], distance: 2 },{ points: [ -1, 0 ], distance: 1 },{ points: [ 3, -5 ], distance: 5.830951894845301 },{ points: [ -2, -3 ], distance: 3.605551275463989 },{ points: [ 3, 8 ], distance: 8.54400374531753 } ]

Sorting The Data

It’s evident from our returned data that although we have got the distances for all points, we can see which one is the closest point ([-1,0]), however it’s not actually any use to the computer. Let’s assume we have 1,000 points to analyse, would you be able to look at a long screen of data and pick out the closest? I would assume not, unless you’re a wizard in which case congratulations, you probably don’t need to read on.

  • heapSort — main call to our heap sort algorithm
  • heapify — Iterate half way through the dataset backwards (only targetting parent nodes)
  • minHeapify — Evaluation of each node and it’s children to determine whether the node is in order
  • swap — Performs the swap on the nodes when called

swap()

Swap is the fundamental operation of our algorithm and follows a standard swap format:

minHeapify()

Here we do our analysis on the points distance vector unit, it’s where we analyse each node of the binary tree to see which value is smallest. A while loop is used inside this function as we need to perform at least 2 checks on each node to evaluate whether all three nodes have been compared against each other. When the largest node of the three is in the parent position, the loop will break:

heapSort()

The heapsort algorithm will return a promise, the reason for this is because JavaScript is asynchronous and it cannot be guaranteed how long the sorting operation will take, however it has a Big O notation of:

O(n log n)

heapify()

You may of noticed in the heapSort() function that we first call heapify and then subsequently call minHeapify() again, why is this? Well, the call to heapify calls the following function:

(data.length / 2)
first child: index * 2 + 1
second child: index * 2 + 2
parent node: index

Finishing Our Program

Now that we have our heap sort algorithm in place and ready to use, the last thing is to finalize the kPoints function like so:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store