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

Question

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

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

Answer 1

JavaScript 中没有任何“内置”的东西具有优先级队列的名称。最接近的原生对象是带有 array-index 键的普通对象。

这有一些限制：

• 优先级队列的键必须是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 中的本机优先级队列行为非常接近。或者，您当然可以添加一个库，或者抛出您自己的优先级队列的实现。例如，在 Efficient way to Implement Priority Queue in Javascript? 您会找到一些实现。我还在那里发布了我的堆实现。

Answer 2

JavaScript 中高效的优先级队列实现

您可以使用二叉堆在 JavaScript 中高效地实现优先级队列。以下代码演示了使用自定义比较器函数支持最小堆和最大堆的灵活实现：

class PriorityQueue {
  /**
   * @template T
   * @typedef {function(T, T): number} Comparator
   */

  /**
   * @param {Comparator<T>} [comparator=(a, b) => a - b]
   */
  constructor(comparator = (a, b) => a - b) {
    this.pq = [];
    this.comparator = comparator;
  }

  push(value) {
    this.pq.push(value);
    this.heapifyUp();
  }

  pop() {
    if (this.isEmpty()) return null;
    if (this.pq.length === 1) return this.pq.pop();

    const root = this.pq[0];
    this.pq[0] = this.pq.pop();
    this.heapifyDown();
    return root;
  }

  size() {
    return this.pq.length;
  }

  isEmpty() {
    return this.pq.length === 0;
  }

  peek() {
    return this.isEmpty() ? null : this.pq[0];
  }

  pushPop(value) {
    if (this.isEmpty()) {
      this.pq.push(value);
      return null;
    }

    const root = this.pq[0];
    this.pq[0] = value;
    this.heapifyDown();
    return root;
  }

  heapifyUp() {
    let currentIndex = this.pq.length - 1;
    while (currentIndex > 0) {
      const parentIndex = (currentIndex - 1) >> 1;
      if (this.comparator(this.pq[currentIndex], this.pq[parentIndex]) < 0) {
        this.swap(currentIndex, parentIndex);
        currentIndex = parentIndex;
      } else break;
    }
  }

  heapifyDown() {
    let currentIndex = 0;
    while (true) {
      const leftChildIndex = (currentIndex << 1) + 1;
      const rightChildIndex = (currentIndex << 1) + 2;
      let smallestChildIndex = currentIndex;

      if (
        leftChildIndex < this.pq.length &&
        this.comparator(this.pq[leftChildIndex], this.pq[smallestChildIndex]) < 0
      ) {
        smallestChildIndex = leftChildIndex;
      }

      if (
        rightChildIndex < this.pq.length &&
        this.comparator(this.pq[rightChildIndex], this.pq[smallestChildIndex]) < 0
      ) {
        smallestChildIndex = rightChildIndex;
      }

      if (currentIndex !== smallestChildIndex) {
        this.swap(currentIndex, smallestChildIndex);
        currentIndex = smallestChildIndex;
      } else break;
    }
  }

  swap(i, j) {
    [this.pq[i], this.pq[j]] = [this.pq[j], this.pq[i]];
  }
}

主要特点

• 灵活性：

  comparator

  允许您定义自定义优先级逻辑。例如，

  (a, b) => b - a

  使其成为最大堆。
• 效率：像

  push

  和

  pop

  这样的操作是O(log n)，而

  peek

  是O(1)。
• 通用设计：此类可以使用合适的比较器处理任何数据类型。

用例

该优先级队列可用于任务调度、图算法（例如Dijkstra最短路径）以及需要动态优先级的模拟等场景。

有关更多详细信息和示例，您可以参考有关 JavaScript 中的优先级队列的博客文章，其中深入介绍了此实现及其应用。

Answer 3

JavaScript 任务队列实现：优先级和优化代码执行

const taskQueue = [];

function enqueueTask(task, priority = 0) {
  taskQueue.push({ task, priority });
  taskQueue.sort((a, b) => a.priority - b.priority);
}

async function processQueue() {
  while (taskQueue.length > 0) {
    const { task, priority } = taskQueue.shift();
    const startTime = performance.now();
    await task();
    const endTime = performance.now();
    const executionTime = endTime - startTime;
    console.log(`Task with priority ${priority} executed in ${executionTime.toFixed(2)} ms`);
  }
}

function task1() {
  return new Promise(resolve => {
    setTimeout(() => {
      console.log("Executing Task 1");
      resolve();
    }, 2000);
  });
}

function task2() {
  console.log("Executing Task 2");
}

function task3() {
  return new Promise(resolve => {
    setTimeout(() => {
      console.log("Executing Task 3");
      resolve();
    }, 1500);
  });
}

function task4() {
  console.log("Executing Task 4");
}

enqueueTask(() => task1(), 2);
enqueueTask(() => task2(), 1);
enqueueTask(() => task3(), 3);
enqueueTask(() => task4(), 0);

processQueue();