堆是怎么知道该怎么分类的？

Question

如果这个问题听起来含糊不清，我很抱歉。我目前正在使用Javascript创建一个A*路径查找算法。我有一个对象列表，每个对象都有一个属性f，我想使用min堆数据结构对列表进行排序。

我不明白的是如何修改排序的基础。我提到的对象具有多个属性，例如h和g。有没有我不知道的符号？我使用npm下载了堆包。

到目前为止，我得到的是：

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
}

我试图替换的代码(出于性能原因)是：

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

如有任何指导，我将不胜感激。谢谢。

Answer 1

看一下文档，它说，如果没有通过构造函数传递比较函数，那么所使用的数据结构是min-heap。如果要传递一个函数，堆将根据该函数构建。

来自https://www.npmjs.com/package/heap

构造函数接收比较函数作为可选参数。如果省略，堆将作为最小堆构建，这意味着将首先弹出最小的元素。

和

如果提供比较函数，则将根据比较函数的返回值构建堆。

这个“比较函数”似乎与JavaScript .sort()非常相似。使用JavaScript .sort()，您将传入一个比较两个值的函数，并根据条件返回a-1、1或0。这些返回值决定元素A的索引是向上还是向下移动，反之亦然。

来源：对象/数组/排序

此外，查看文档时，您的if(!heap.empty)需要是if(!heap.empty())。

编辑：

下面是堆文档中的一个示例排序/比较函数。它所做的就是把数字从最小到最大。

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