Home Manual Reference Source Test

Overview

Installation

Can be managed using jspm or npm.

jspm

jspm install npm:@heap-data-structure/d-ary-heap

npm

npm install @heap-data-structure/d-ary-heap --save

Usage

The code needs a ES2015+ polyfill to work, for example regenerator-runtime/runtime.

await import( 'regenerator-runtime/runtime.js' ) ;
// or
import 'regenerator-runtime/runtime.js' ;

Then

const daryheap = await import( '@heap-data-structure/d-ary-heap' ) ;
// or
import daryheap from '@heap-data-structure/d-ary-heap' ;

Examples

Functions

// Builds a heap in O(n) operations.
makeheap( arity , compare , swap , array , left , right ) ;

// Merges heaps at intervals [i, j[ and [j, k[ in array *a* into a new heap at interval [i, k[.
merge( arity , compare , swap , array , left , middle , right ) ;

// Computes which child is the smallest according to a comparison function.
nextchild( arity , compare , swap , array , left , right ) ;

// Pops the root from a d-ary heap.
pop( arity , compare , swap , array , left , right ) ;

// Sifts a node up to the root as if its priority was the highest.
pull( arity , compare , swap , array , left , right , target ) ;

// Inserts the jth element of an array in an existing dary heap in interval [i, j[.
push( arity , compare , swap , array , left , right ) ;

// Removes a target element from a d-ary heap.
remove( arity , compare , swap , array , left , right , target ) ;

// Sifts down a node.
siftdown( arity , compare , swap , array , left , right , target ) ;

// Sifts up a node.
siftup( arity , compare , swap , array , left , right , target ) ;

// Sorted iterator on the elements of the input array.
// If only the first k elements are read the cost is O(n + k log n).
// The array is mutated.
sorted( arity , compare , swap , array , left , right ) ;

ADT

// can choose between 2 different implementations
//
//   - DAryHeap
//      # head -> value
//      # headreference -> reference
//      # pop -> value
//      # popreference -> reference
//      # push( value ) -> reference
//      # pushreference( reference )
//      # merge( other )
//      # update( reference , value )
//      # decreasekey( reference , value )
//      # increasekey( reference , value )
//      # delete( reference )
//
//   - DAryHeapWithoutReferences
//      # head -> value
//      # pop -> value
//      # push( value )
//      # merge( other )

let heap = new daryheap. ... ( 2 , compare.increasing ) ;
//                         ^            ^
//                       arity       ordering