Ts-bin-heap NPM

ts-bin-heap

A flexible binary-heap. This data-structure is optimized for the retrieval of either the maximum or the minimum

This package contains functions for creating binary-heaps conforming to the BinaryHeap<T> interface

The main methods of BinaryHeap<T> are simply push and pop. You can push items into the heap, and you can pop items from it. The item that is popped will always be either the maximum or the minimum item in the collection.

Auto-generated documentation

Usage

import { createBinaryHeap } from 'ts-bin-heap'

`createBinaryHeap`

The createBinaryHeap function should be all you need to get started.

Play with this example on codesandbox.io.

Say we have a collection of people:

const people: Person[] = [
  {
    name: 'will',
    priority: 10
  },
  {
    name: 'jack',
    priority: 7
  },
  {
    name: 'nicole',
    priority: 8
  },
  {
    name: 'poppy',
    priority: 44
  }
]

Now we can make a binary heap to hold these people, using the rankSelector parameter to pass in a function that calculates the order ranking of the items that are inserted.

const heap: BinaryHeap<Person> = createBinaryHeap<Person>(person => person.priority)
people.forEach(p => heap.push(p))
const lowestPriorityUser = heap.pop() // returns {name: 'jack', priority: 7}

The full definition of createBinaryHeap is as follows:

createBinaryHeap<T>(
  rankSelector: (item: T) => number,
  type: 'min' | 'max' = 'min',
  stable: boolean = true
): BinaryHeap<T>

`rankSelector`

Required : A method that takes an item and selects from it an order ranking.

`type`

One of "min" or "max". Changes the behaviour of pop to return either the minimum or the maximum item in the collection. Defaults to "min"

`stable`

Binary heaps are inherently unstable. This means that items that are inserted with equal order ranking will be popped in an indeterminate order. It is possible to make the heap stable by tagging each entry with an "order-of-insertion" field, and using this as a secondary comparison when selecting the maximum/minimum item. This option is switched on by default. Supplying false here will revert to the faster, unstable version.