Class Heap<T>

A max binary heap.

A heap data structure is a tree with the property that every parent node’s value is greater than or equal to (for a max heap) the values of its children nodes. (For a min heap, parents would be less than or equal to each of their children.) Every node in a binary heap has 2 children or less. Being a tree, every node in a heap has exactly one parent, with the exception of the root node, which has no parent.

See

https://en.wikipedia.org/wiki/Heap_(data_structure)

Typeparam

T the type of node value in this Heap

Type Parameters

  • T

Constructors

constructor

Properties

#internal comparator

Accessors

count

Methods

#internalDelete #internalSwap #siftDown #siftUp clear inspect peek pop push remove removeAll resift

Constructors

constructor

  • new Heap<T>(comparator, ...initial_items): Heap<T>

  • Construct a new Heap object.

    Type Parameters

    • T

    Parameters

    • comparator: Comparator<T>

      a Comparator function comparing nodes’ values

    • Rest ...initial_items: readonly T[]

      any optional items to start with

    Returns Heap<T>

Properties

Private Readonly #internal

#internal: T[] = []

Internal implementation of this Heap.

This class is implemented with a JS Array, defining node relationships implicitly. Specifically, given a parent node with index i, its two child nodes have indices 2 * i + 1 and 2 * i + 2. Using an array is more performant than having nodes hold explicit references to their children.

Private Readonly comparator

comparator: Comparator<T>

a Comparator function comparing nodes’ values

Accessors

count

  • get count(): number

  • The number of nodes in this Heap.

    Returns number

Methods

Private #internalDelete

  • #internalDelete(index): void

  • Parameters

    • index: number

    Returns void

Private #internalSwap

  • #internalSwap(index_a, index_b): void

  • Parameters

    • index_a: number
    • index_b: number

    Returns void

Private #siftDown

  • #siftDown(index): void

  • Parameters

    • index: number

    Returns void

Private #siftUp

  • #siftUp(index): void

  • Parameters

    • index: number

    Returns void

clear

  • clear(): this

  • Remove all nodes from this Heap.

    Returns this

    this

inspect

  • inspect(): T[]

  • Return a shallow copy of this Heap’s internal implementation. The returned array is only a copy, so mutating it will not mutate this Heap. However, the array’s items are the same references as this Heap’s nodes, so any mutations of them will be observed.

    Returns T[]

    a copy of this Heap’s array

peek

  • peek(): T

  • Return the maximal node in this Heap, without modifying the Heap.

    Returns T

    the maximal node

    Throws

    if this Heap is empty

pop

  • pop(): [Heap<T>, T]

  • Remove the maximal node from this Heap.

    Returns [Heap<T>, T]

    [this, node], where node is the maximal node

    Throws

    if this Heap is empty

push

  • push(...nodes): this

  • Add the given items to this Heap and return this Heap.

    Parameters

    • Rest ...nodes: readonly T[]

      the items to add

    Returns this

    this

remove

  • remove(node): [Heap<T>, T]

  • Remove the given node.

    Parameters

    • node: T

      the node to remove

    Returns [Heap<T>, T]

    [this, node], where node is the removed node

    Throws

    if the node is not in this Heap

    Throws

    if this Heap is empty

  • remove(predicate): [Heap<T>, T]

  • Remove the first node that satisfies the given predicate.

    Parameters

    • predicate: ((node, src) => boolean)

      a function to find nodes

        • (node, src): boolean

        • Parameters

          • node: T
          • src: this

          Returns boolean

    Returns [Heap<T>, T]

    [this, node], where node is the removed node

    Throws

    if no node satisfies the predicate

    Throws

    if this Heap is empty

removeAll

  • removeAll(nodes): [Heap<T>, T[]]

  • Remove all of the given nodes.

    Parameters

    • nodes: readonly T[]

      the nodes to remove

    Returns [Heap<T>, T[]]

    [this, nodes], where nodes is a list of the removed nodes

    Throws

    if this Heap is empty

  • removeAll(predicate): [Heap<T>, T[]]

  • Remove all nodes that satisfy the given predicate.

    Parameters

    • predicate: ((node, src) => boolean)

      a function to find nodes

        • (node, src): boolean

        • Parameters

          • node: T
          • src: this

          Returns boolean

    Returns [Heap<T>, T[]]

    [this, nodes], where nodes is a list of the removed nodes

    Throws

    if this Heap is empty

resift

  • resift(): this

  • Reorders the nodes in this Heap to a valid arrangement. Should be called whenever one or more nodes have changed/mutated in a way that affects this Heap’s “max heap” property (that is, that every node should be greater than its children). If the nodes are already in a valid order, nothing is changed.

    Returns this

    this

Settings

Member Visibility

Theme

On This Page

constructor#internalcomparatorcount#internalDelete#internalSwap#siftDown#siftUpclearinspectpeekpoppushremoveremoveAllresift