Introducing Socket Firewall: Free, Proactive Protection for Your Software Supply Chain.Learn More
Socket
Book a DemoInstallSign in
Socket

@datastructures-js/priority-queue

Package Overview
Dependencies
Maintainers
1
Versions
34
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@datastructures-js/priority-queue

a performant priority queue implementation using a Heap data structure.

Source
npmnpm
Version
5.4.0
Version published
Weekly downloads
148K
-0.41%
Maintainers
1
Weekly downloads
 
Created
Source

@datastructures-js/priority-queue

build:? npm npm npm

A performant priority queue implementation using a Heap data structure.

Contents

Install

npm install --save @datastructures-js/priority-queue

API

PriorityQueue in this repo is implemented as 3 types:

  • PriorityQueue that accepts a custom comparator between elements.
  • MinPriorityQueue which considers an element with smaller priority number as higher in priority.
  • MaxPriorityQueue which cosiders an element with bigger priority number as higher in priority.

require

const {
  PriorityQueue,
  MinPriorityQueue,
  MaxPriorityQueue
} = require('@datastructures-js/priority-queue');

import

import {
  PriorityQueue,
  MinPriorityQueue,
  MaxPriorityQueue,
  PriorityQueueOptions, // queue options interface
  PriorityQueueItem // queue item interface for min/max queue
} from '@datastructures-js/priority-queue';

constructor

PriorityQueue

The constructor requires a compare callback to compare between queue elements. compare works similar to javascript sort callback: returning a number less or equal 0, means do not swap.

JS
// empty queue with comparator
const employeesQueue = new PriorityQueue({
  compare: (e1, e2) => {
    if (e1.salary > e2.salary) return -1; // do not swap
    if (e1.salary < e2.salary) return 1; // swap

    // salaries are the same, compare rank
    return e1.rank < e2.rank ? 1 : -1;
  }
});
TS
// queued element type
interface Employee {
  name: string;
  salary: number;
  rank: number;
}

// empty queue with comparator
const employeesQueue = new PriorityQueue<Employee>({
  compare: (e1: Employee, e2: Employee): number => {
    if (e1.salary > e2.salary) return -1; // do not swap
    if (e1.salary < e2.salary) return 1; // swap

    // salaries are the same, compare rank
    return e1.rank < e2.rank ? 1 : -1;
  }
});

MinPriorityQueue/MaxPriorityQueue

The constructor accepts a priority callback option to get the numeric priority from the queued element. If not passed, the constructor adds a default priority callback that returns the numeric value of the element itself. Use this queue type when the priority is a known value and does not require complex comparison.

JS
// empty queue with priority is the element value itself.
const numbersQueue = new MinPriorityQueue();

// empty queue, will provide priority in .enqueue
const patientsQueue = new MinPriorityQueue();

// empty queue with priority returned from a prop of the queued object
const biddersQueue = new MaxPriorityQueue({ priority: (bid) => bid.value });
TS
const numbersQueue = new MinPriorityQueue<number>();

const patientsQueue = new MinPriorityQueue<string>();

interface Bid {
  name: string;
  value: number;
}
const biddersQueue = new MaxPriorityQueue<Bid>({
  priority: (bid: Bid) => bid.value
});

from(entries)

Creates a priority queue from an array of element-priority pairs.

MaxPriorityQueue.from([
  ['Alice', 19],
  ['Bob', 18],
  ['Charles', 20]
])
// { priority: 20, element: 'Charles' }, 
// { priority: 19, element: 'Alice' }, 
// { priority: 18, element: 'Bob' }

MinPriorityQueue.from([
  ['Alice', 19],
  ['Bob', 18],
  ['Charles', 20]
])
// { priority: 18, element: 'Bob' },
// { priority: 19, element: 'Alice' }, 
// { priority: 20, element: 'Charles' },

.enqueue

PriorityQueue - .enqueue(element)

adds an element based on its comparison with other elements in the queue.

paramsreturnruntime
element: TPriorityQueue<T>O(log(n))
employeesQueue
  .enqueue({ name: 'employee 1', salary: 2000, rank: 1 })
  .enqueue({ name: 'employee 2', salary: 1500, rank: 0 })
  .enqueue({ name: 'employee 3', salary: 4000, rank: 4 })
  .enqueue({ name: 'employee 4', salary: 2000, rank: 2 })
  .enqueue({ name: 'employee 5', salary: 3000, rank: 3 });

MinPriorityQueue/MaxPriorityQueue - .enqueue(element[, priority])

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.

paramsreturnruntime
element: T
priority: number
MinPriorityQueue<T> | MaxPriorityQueue<T>O(log(n))
// MinPriorityQueue Example, where priority is the number element itself
numbersQueue
  .enqueue(10)
  .enqueue(-7)
  .enqueue(2)
  .enqueue(-1)
  .enqueue(-17)
  .enqueue(33);

// 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'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 });

.front()

returns the element with highest priority in the queue.

PriorityQueue

returnruntime
TO(1)
console.log(employeesQueue.dequeue()); // { name: 'employee 3', salary: 4000, rank: 4 }

MinPriorityQueue/MaxPriorityQueue

returnruntime
PriorityQueueItem<T>O(1)
console.log(numbersQueue.front()); // { priority: -17, element: -17 }

console.log(patientsQueue.front()); // { priority: 1, element: 'patient y' }

console.log(biddersQueue.front()); // { priority: 3500, element: { name: 'bidder z', value: 3500 } }

.back()

returns an element with a lowest priority in the queue.

PriorityQueue

returnruntime
TO(1)
console.log(employeesQueue.back()); // { name: 'employee 2', salary: 1500, rank: 0 }

MinPriorityQueue/MaxPriorityQueue

returnruntime
PriorityQueueItem<T>O(1)
console.log(numbersQueue.back()); // { priority: 33, element: 33 }

patientsQueue.enqueue('patient m', 4); // lowest priority
patientsQueue.enqueue('patient c', 4); // lowest priority
console.log(patientsQueue.back()); // { priority: 4, element: 'patient c' }

biddersQueue.enqueue({ name: 'bidder m', value: 1000 }); // lowest priority
biddersQueue.enqueue({ name: 'bidder c', value: 1000 }); // lowest priority
console.log(biddersQueue.back()); // { priority: 1000, element: { name: 'bidder y', value: 1000 } }

.dequeue()

removes and returns the element with highest priority in the queue.

PriorityQueue

returnruntime
TO(log(n))
console.log(employeesQueue.dequeue()); // { name: 'employee 3', salary: 4000, rank: 4 }
console.log(employeesQueue.dequeue()); // { name: 'employee 5', salary: 3000, rank: 3 }
console.log(employeesQueue.dequeue()); // { name: 'employee 4', salary: 2000, rank: 2 }
console.log(employeesQueue.dequeue()); // { name: 'employee 1', salary: 2000, rank: 1 }
console.log(employeesQueue.dequeue()); // { name: 'employee 2', salary: 1500, rank: 0 }

MinPriorityQueue/MaxPriorityQueue

returnruntime
PriorityQueueItem<T>O(log(n))
console.log(numbersQueue.dequeue()); // { priority: -17, element: -17 }
console.log(numbersQueue.front()); // { priority: -7, element: -7 }

console.log(patientsQueue.dequeue()); // { priority: 1, element: 'patient y' }
console.log(patientsQueue.front()); // { priority: 2, element: 'patient x' }

console.log(biddersQueue.dequeue()); // { priority: 3500, element: { name: 'bidder z', value: 3500 } }
console.log(biddersQueue.front()); // { priority: 3000, element: { name: 'bidder x', value: 3000 } }

.isEmpty()

checks if the queue is empty.

returnruntime
booleanO(1)
console.log(numbersQueue.isEmpty()); // false

console.log(patientsQueue.isEmpty()); // false

console.log(biddersQueue.isEmpty()); // false

.size()

returns the number of elements in the queue.

returnruntime
numberO(1)
console.log(numbersQueue.size()); // 5

console.log(patientsQueue.size()); // 5

console.log(biddersQueue.size()); // 5

.toArray()

returns a sorted array of elements by their priorities from highest to lowest.

PriorityQueue

returnruntime
T[]O(n*log(n))
console.log(employeesQueue.toArray());
/*
[
  { name: 'employee 3', salary: 4000, rank: 4 },
  { name: 'employee 5', salary: 3000, rank: 3 },
  { name: 'employee 4', salary: 2000, rank: 2 },
  { name: 'employee 1', salary: 2000, rank: 1 },
  { name: 'employee 2', salary: 1500, rank: 0 }
]
*/

MinPriorityQueue/MaxPriorityQueue

returnruntime
PriorityQueueItem<T>[]O(n*log(n))
console.log(numbersQueue.toArray());
/*
[
  { priority: -7, element: -7 },
  { priority: -1, element: -1 },
  { priority: 2, element: 2 },
  { priority: 10, element: 10 },
  { priority: 33, element: 33 }
]
*/

console.log(patientsQueue.toArray());
/*
[
  { priority: 2, element: 'patient x' },
  { priority: 3, element: 'patient z' },
  { priority: 4, element: 'patient c' },
  { priority: 4, element: 'patient w' },
  { priority: 4, element: 'patient m' }
]
*/

console.log(biddersQueue.toArray());
/*
[
  { priority: 3000, element: { name: 'bidder x', value: 3000 } },
  { priority: 2500, element: { name: 'bidder w', value: 2500 } },
  { priority: 1000, element: { name: 'bidder y', value: 1000 } },
  { priority: 1000, element: { name: 'bidder m', value: 1000 } },
  { priority: 1000, element: { name: 'bidder c', value: 1000 } }
]
*/

.clear()

clears all elements in the queue.

runtime
O(1)
numbersQueue.clear();
console.log(numbersQueue.size()); // 0
console.log(numbersQueue.front()); // null
console.log(numbersQueue.dequeue()); // null

patientsQueue.clear();
console.log(patientsQueue.size()); // 0
console.log(patientsQueue.front()); // null
console.log(patientsQueue.dequeue()); // null

biddersQueue.clear();
console.log(biddersQueue.size()); // 0
console.log(biddersQueue.front()); // null
console.log(biddersQueue.dequeue()); // null

Build

grunt build

License

The MIT License. Full License is here

Keywords

queue

FAQs

Package last updated on 08 Jan 2024

Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts