Heap 如何知道要根据什么进行排序？

Question

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

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

到目前为止我拥有的是：

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

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.

和

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

看起来这个 "comparison function" 与 JavaScript .sort() 非常相似。使用 JavaScript .sort()，您传入一个比较两个值的函数，并根据条件 return 为 -1、1 或 0。这些 return 值确定元素 A 的索引是向上移动还是向下移动，反之亦然。

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

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

编辑：

这里是堆文档中的一个示例 sort/comparison 函数。它所做的只是从小到大组织数字。

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

Heap 如何知道要根据什么进行排序？

How does Heap know what to sort by?

javascript

sorting

heap

priority-queue

heapsort