lib: add internal PriorityQueue class

An efficient JS implementation of a binary heap on top of an array with
worst-case O(log n) runtime for all operations, including arbitrary
item removal (unlike O(n) for most binary heap array implementations).

PR-URL: https://github.com/nodejs/node/pull/20555
Fixes: https://github.com/nodejs/node/issues/16105
Reviewed-By: Ben Noordhuis <info@bnoordhuis.nl>
Reviewed-By: Jeremiah Senkpiel <fishrock123@rocketmail.com>
Reviewed-By: Matteo Collina <matteo.collina@gmail.com>
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Ruben Bridgewater <ruben@bridgewater.de>

1 files changed, 18 insertions, 0 deletions

diff --git a/benchmark/util/priority-queue.js b/benchmark/util/priority-queue.js
new file mode 100644
index 0000000000..51a696439a
--- /dev/null
+++ b/benchmark/util/priority-queue.js
@@ -0,0 +1,18 @@
+'use strict';
+
+const common = require('../common');
+
+const bench = common.createBenchmark(main, {
+  n: [1e6]
+}, { flags: ['--expose-internals'] });
+
+function main({ n, type }) {
+  const PriorityQueue = require('internal/priority_queue');
+  const queue = new PriorityQueue();
+  bench.start();
+  for (var i = 0; i < n; i++)
+    queue.insert(Math.random() * 1e7 | 0);
+  for (i = 0; i < n; i++)
+    queue.shift();
+  bench.end(n);
+}