From 6f6f7f749bd6847278836832542116f371ab3aa6 Mon Sep 17 00:00:00 2001
From: Anatoli Papirovski <apapirovski@mac.com>
Date: Sat, 5 May 2018 10:09:44 +0200
Subject: 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>
---
 benchmark/util/priority-queue.js | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)
 create mode 100644 benchmark/util/priority-queue.js

(limited to 'benchmark')

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);
+}
-- 
cgit v1.2.3