如何在javascript中使用内置的优先队列?

Question

如何在javascript中使用内置的优先级队列

在chrome中，我无法运行内置在javascript中的pq

Answer 1

没有"内置"。在JavaScript中以优先队列的名字命名。最接近的原生对象是带有arrayindex键的普通对象。

有一些限制:

• 优先级队列的键必须是32位范围内的无符号整数
• 优先级队列不能容纳两个具有相同键的项目，除非你添加额外的逻辑来处理。

这是如何工作的:

function pqInsert(pq, key, value) {
if (String(Math.abs(+key | 0)) != String(key)) throw "Key must be unsigned 32 bit integer";
if (pq[key] !== undefined) throw "Duplicate key";
pq[key] = value;
}
function pqLeastKey(pq) {
for (const key in pq) { // Iterate numeric keys in order
return key; // Exit in first iteration
}
}
function pqExtract(pq) {
const key = pqLeastKey(pq);
const value = pq[key]; // Get value of least key
delete pq[key]; // Remove it
return [key, value];
}
const pq = {};
// I/O handling
const [keyInput, valueInput, addButton, removeButton, br, output] =
document.body.children;
addButton.onclick = () => {
pqInsert(pq, keyInput.value, valueInput.value);
keyInput.value = valueInput.value = "";
output.textContent = JSON.stringify(pq, null, 2);
}
removeButton.onclick = () => {
[keyInput.value, valueInput.value] = pqExtract(pq);
output.textContent = JSON.stringify(pq, null, 2);
};

input { width: 5em }

Key: <input type="number" min="0"> Value: <input> <button>Add</button>
<button>Extract minimum</button><br>
Queue: <pre>{}</pre>

这是JavaScript中最接近原生优先队列行为的地方。当然，您也可以添加一个库，或者抛出您自己的优先级队列实现。例如，在Javascript中实现优先队列的有效方法?您将找到一些实现。我还在那里发布了我的堆实现。