functional-priority-queue

A confluently persistent functional priority queue.

Technical details

This priority queue is implemented using a pairing heap, though because it uses a pure functional interface it does not support the decrease-key function (as locating a node within the heap without maintaining cyclic pointers is expensive).

Example

var fpq = require('functional-priority-queue')

Installation

This module works in any node-flavored CommonJS environment, including node.js, iojs and browserify. You can install it using the npm package manager with the following command:

npm i functional-priority-queue

API

var fpq = require('functional-priority-queue')

var pq = fpq(keys, values)

Creates a new functional priority queue

• keys is an array of weights which are used to order the elements in the priority queue
• values is an array of values which are ascoiated to the keys

Returns A new priority queue

Time Complexity O(keys.length)

pq.minKey

The key of the smallest element in the priority queue

pq.minValue

The value of the smallest element in the priority queue

var next = fpq.push(pq, key, value)

Adds an item to the priority queue

• pq is the priority queue into which we are inserting
• key is the key we are inserting into the priority queue
• value is the value we are inserting into the priority queue

Returns A new priority queue with the pair (key, value) added to it

Time Complexity O(1)

var next = fpq.pop(pq)

Removes the top element from a priority queue

• pq is a priority queue which we are removing from

Returns A copy of pq with the minimal element deleted

Time Complexity O(log(n)) amortized

var next = fpq.merge(pq1, pq2, ...pqn)

Merges a list of priority queues into a single priority queue

• pq1, pq2, ...pqn is a list of n priority queues

Returns A single priority queue whose contents are equal to all the input priority queues combined

Time Complexity O(n)

License

(c) 2015 Mikola Lysenko. MIT License