New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

@datastructures-js/priority-queue

Package Overview
Dependencies
Maintainers
1
Versions
31
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@datastructures-js/priority-queue - npm Package Compare versions

Comparing version 4.1.2 to 5.0.0

13

CHANGELOG.md

@@ -9,2 +9,15 @@ # Changelog

## [5.0.0] - 2021-01-24
### Changed
- upgrade heap to latest major version.
- `.enqueue` can now be chanined.
### Added
- a default priority callback that returns the element itself if no callback is provided.
### Fixed
- cleaner error messages.
- README
- jsdoc
## [4.1.2] - 2020-09-22

@@ -11,0 +24,0 @@ ### Fixed

4

package.json
{
"name": "@datastructures-js/priority-queue",
"version": "4.1.2",
"version": "5.0.0",
"description": "a performant priority queue implementation using a Heap data structure.",

@@ -38,4 +38,4 @@ "main": "index.js",

"dependencies": {
"@datastructures-js/heap": "^2.0.0"
"@datastructures-js/heap": "^3.0.0"
}
}

213

README.md

@@ -11,5 +11,5 @@ # @datastructures-js/priority-queue

* [Install](#install)
* [require](#require)
* [import](#import)
* [API](#api)
* [require](#require)
* [import](#import)
* [Construction](#construction)

@@ -49,11 +49,9 @@ * [.enqueue(element[, priority])](#enqueueelement-priority)

### Construction
The constructor can accept a callback to get the priority from the queued element. If not passed, the priortiy should be passed with `.enqueue`.
The constructor accepts a callback to get the numeric priority from the queued element. If not passed, the constructor adds a default priority callback that returns the value of the element itself.
#### Example
```js
// the priority not part of the enqueued element
const patientsQueue = new MinPriorityQueue();
// empty queue with priority not being part of the queued element
const patientsQueue = new MinPriorityQueue(); // priority should be provided in .enqueue
// the priority is a prop of the queued element
// empty queue with priority returned from the queued element
const biddersQueue = new MaxPriorityQueue({ priority: (bid) => bid.value });

@@ -63,34 +61,35 @@ ```

### .enqueue(element[, priority])
adds an element with a priority (number) to the queue. Priority is not required here if a priority callback has been defined in the constructor. If passed here in addition to an existing constructor callback, it will override the callback one.
adds an element with a numeric priority to the queue. Priority is not required here if a priority callback has been provided in the constructor. If passed here with a constructor callback, it will override the callback.
<table>
<tr><th align="center" colspan="3">params</th></tr>
<tr><td><b>name</b></td><td><b>type</b></td></tr>
<tr><td>element</td><td>object</td></tr>
<tr><td>priority</td><td>number</td></tr>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
element: any
<br />
priority: number
</td>
<td align="center">MinPriorityQueue | MaxPriorityQueue</td>
<td align="center">O(log(n))</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(log(n))</td>
</tr>
</table>
#### Example
```js
// MinPriorityQueue Example, where priority is the turn for example
patientsQueue.enqueue('patient y', 1); // highest priority
patientsQueue.enqueue('patient z', 3);
patientsQueue.enqueue('patient w', 4); // lowest priority
patientsQueue.enqueue('patient x', 2);
// MinPriorityQueue Example, where priority is the patient's turn
patientsQueue
.enqueue('patient y', 1); // highest priority
.enqueue('patient z', 3);
.enqueue('patient w', 4); // lowest priority
.enqueue('patient x', 2);
// MaxPriorityQueue Example, where priority is the bid for example. Priority is obtained from the callback.
biddersQueue.enqueue({ name: 'bidder y', value: 1000 }); // lowest priority
biddersQueue.enqueue({ name: 'bidder w', value: 2500 });
biddersQueue.enqueue({ name: 'bidder z', value: 3500 }); // highest priority
biddersQueue.enqueue({ name: 'bidder x', value: 3000 });
// MaxPriorityQueue Example, where priority is the bid's value.
biddersQueue
.enqueue({ name: 'bidder y', value: 1000 }); // lowest priority
.enqueue({ name: 'bidder w', value: 2500 });
.enqueue({ name: 'bidder z', value: 3500 }); // highest priority
.enqueue({ name: 'bidder x', value: 3000 });
```

@@ -102,20 +101,12 @@

<table>
<tr><th>return</th><th>description</th></tr>
<tr>
<td>object</td>
<td>object literal with "priority" and "element" props</td>
</tr>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">object</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js

@@ -128,27 +119,19 @@ console.log(patientsQueue.front()); // { priority: 1, element: 'patient y' }

### .back()
returns an element with lowest priority in the queue. If multiple elements exist at the lowest priority, the one that was inserted first will be returned.
returns an element with a lowest priority in the queue.
<table>
<tr><th>return</th><th>description</th></tr>
<tr>
<td>object</td>
<td>object literal with "priority" and "element" props</td>
</tr>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">object</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js
patientsQueue.enqueue('patient m', 4); // lowest priority
patientsQueue.enqueue('patient c', 4); // lowest priority
console.log(patientsQueue.back()); // { priority: 4, element: 'patient w' }
console.log(patientsQueue.back()); // { priority: 4, element: 'patient c' }

@@ -164,20 +147,12 @@ biddersQueue.enqueue({ name: 'bidder m', value: 1000 }); // lowest priority

<table>
<tr><th>return</th><th>description</th></tr>
<tr>
<td>object</td>
<td>object literal with "priority" and "element" props</td>
</tr>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">object</td>
<td align="center">O(log(n))</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(log(n))</td>
</tr>
</table>
#### Example
```js

@@ -195,19 +170,12 @@ console.log(patientsQueue.dequeue()); // { priority: 1, element: 'patient y' }

<table>
<tr><th>return</th></tr>
<tr>
<td>boolean</td>
</tr>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">boolean</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js

@@ -223,19 +191,12 @@ console.log(patientsQueue.isEmpty()); // false

<table>
<tr><th>return</th></tr>
<tr>
<td>number</td>
</tr>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">number</td>
<td align="center">O(1)</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(1)</td>
</tr>
</table>
#### Example
```js

@@ -251,19 +212,12 @@ console.log(patientsQueue.size()); // 5

<table>
<tr><th>return</th><th>description</th></tr>
<tr>
<td>array</td><td>an array of object literals with "priority" & "element" props</td>
</tr>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">array&lt;object&gt;</td>
<td align="center">O(n*log(n))</td>
</tr>
</table>
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>O(n*log(n))</td>
</tr>
</table>
#### Example
```js

@@ -305,3 +259,2 @@ console.log(patientsQueue.toArray());

#### Example

@@ -308,0 +261,0 @@ ```js

1

src/maxPriorityQueue.js
/**
* @datastructures-js/priority-queue
* @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>

@@ -4,0 +3,0 @@ * @license MIT

1

src/minPriorityQueue.js
/**
* @datastructures-js/priority-queue
* @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>

@@ -4,0 +3,0 @@ * @license MIT

76

src/priorityQueue.js
/**
* @datastructures-js/priority-queue
* @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>
* @license MIT
*/
/**
*
* @abstract

@@ -12,11 +9,27 @@ * @class PriorityQueue

class PriorityQueue {
/**
* Creates a priority queue
* @public
* @params {object} [options]
*/
constructor(options = {}) {
const { priority } = options;
if (priority !== undefined && typeof priority !== 'function') {
throw new Error('invalid priority callback');
throw new Error('.constructor expects a valid priority function');
}
this._getPriority = typeof priority === 'function' ? priority : null;
this._priorityCb = priority || ((el) => +el);
}
/**
* @private
* @returns {object}
*/
_getElementWithPriority(node) {
return {
priority: node.key,
element: node.value
};
}
/**
* @public

@@ -38,4 +51,4 @@ * @returns {number}

/**
* Returns an element with highest priority in the queue
* @public
* returns the element with highest priority in the queue
* @returns {object}

@@ -45,13 +58,8 @@ */

if (this.isEmpty()) return null;
const first = this._heap.root();
return {
priority: first.getKey(),
element: first.getValue()
};
return this._getElementWithPriority(this._heap.root());
}
/**
* Returns an element with lowest priority in the queue
* @public
* returns the element with lowest priority in the queue
* @returns {object}

@@ -61,14 +69,9 @@ */

if (this.isEmpty()) return null;
const last = this._heap.leaf();
return {
priority: last.getKey(),
element: last.getValue()
};
return this._getElementWithPriority(this._heap.leaf());
}
/**
* Adds an element to the queue
* @public
* add an element to the queue based on its priority
* @param {object} element
* @param {any} element
* @param {number} p - priority

@@ -79,16 +82,20 @@ * @throws {Error} if priority is not a valid number

if (p && Number.isNaN(+p)) {
throw new Error('invalid priority number');
throw new Error('.enqueue expects a numeric priority');
}
if (Number.isNaN(+p) && this._getPriority === null) {
throw new Error('missing priority number or constructor callback');
if (Number.isNaN(+p) && Number.isNaN(this._priorityCb(element))) {
throw new Error(
'.enqueue expects a numeric priority '
+ 'or a constructor callback that returns a number'
);
}
const priority = !Number.isNaN(+p) ? p : this._getPriority(element);
this._heap.insert(priority, element);
const priority = !Number.isNaN(+p) ? p : this._priorityCb(element);
this._heap.insert(+priority, element);
return this;
}
/**
* Removes and returns an element with highest priority in the queue
* @public
* removes and returns the element with highest priority in the queue
* @returns {object}

@@ -98,13 +105,8 @@ */

if (this.isEmpty()) return null;
const first = this._heap.extractRoot();
return {
priority: first.getKey(),
element: first.getValue()
};
return this._getElementWithPriority(this._heap.extractRoot());
}
/**
* Returns a sorted list of elements from highest to lowest priority
* @public
* returns an sorted list of elements from highest priority to lowest
* @returns {array}

@@ -116,3 +118,3 @@ */

.sort()
.map((n) => ({ priority: n.getKey(), element: n.getValue() }))
.map((n) => this._getElementWithPriority(n))
.reverse();

@@ -122,4 +124,4 @@ }

/**
* Clears the queue
* @public
* clears the queue
*/

@@ -126,0 +128,0 @@ clear() {

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc