How does Heap know what to sort by?

Question

My apologies if this question sounds vague. I am currently using Javascript to create an A* pathfinding algorithm. I have a list of Objects that each have an attribute f and I would like to use the minheap data structure to sort through a list.

What I don't understand is how to modify what to base the sorting on. The Objects I mentioned have multiple attributes, like h and g for instance. Is there a notation that I am not aware of? I downloaded the heap package using npm.

So far what I have is:

var Heap = require('heap');
var heap = new Heap();
.
.
.
heap.push(start) // start is an object, specifically a Cell inside a grid

if(!heap.empty){
  // where I am having trouble
}

And the code I am trying to substitute (for performance reasons) is:

var winner = 0;
for (var i = 0; i < openSet.length; i++) {
    if (openSet[i].f < openSet[winner].f) {
        winner = i;
    }
}

I would appreciate any guidance. Thank you.

Answer 1

Taking a look at the docs, it says that if no comparison function is passed through the constructor, the data structure used is a min-heap. If you were to pass in a function, the heap would be built according to that function.

From https://www.npmjs.com/package/heap

The constructor receives a comparison function as an optional parameter. If omitted, the heap is built as a min-heap, which means that the smallest element will be popped out first.

and

If the comparison function is supplied, the heap will be built according to the return value of the comparison function.

It seems like this "comparison function" is very similar to the JavaScript .sort(). With the JavaScript .sort(), you pass in a function that compares two values and, depending on the conditions, will return either a -1, 1, or 0. Those return values determine if the index of element A is going to be moved up or down and vice versa with element B.

Source: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

Also, looking at the docs your if(!heap.empty) needs to be if(!heap.empty()).

Edit:

Here is an example sort/comparison function from the heap docs. All it does is organize numbers from smallest to greatest.

function cmp(a, b) {
    return a - b;
}