Options
All
  • Public
  • Public/Protected
  • All
Menu

@shlappas/heap

Index

Type aliases

Functions

Type aliases

Comparator

Comparator<T>: (a: T, b: T) => number

A Function to compare two values of the same type T.

The return value should be a number, v, such that

  • If value a is less than value b, v is negative.
  • If value a is greater than value b, v is positive.
  • If value a is equal to value b, v is zero.

Type parameters

  • T

Type declaration

    • (a: T, b: T): number

    • Parameters

      • a: T
      • b: T

      Returns number

Functions

Const defaultCmp

  • defaultCmp(a: unknown, b: unknown): number

  • The default comparator for the heap actions. It is defined this way to be consistent with the Array.prototype.sort() function.

    Parameters

    • a: unknown
    • b: unknown

    Returns number

heapify

  • "Sorts" an array in-place into a min-heap according to the passed comparator.

    Type parameters

    • T

    Parameters

    Returns void

heappop

  • heappop<T>(heap: T[], cmp?: Comparator<T>): T | undefined

  • Removes and returns the minimum element from the heap while maintaining the heap substructure.

    Type parameters

    • T

    Parameters

    Returns T | undefined

heappush

  • heappush<T>(heap: T[], value: T, cmp?: Comparator<T>): void

  • Adds a new element to a heap while keeping the heap substructure (according to the comparator).

    Type parameters

    • T

    Parameters

    Returns void

heappushpop

  • heappushpop<T>(heap: T[], value: T, cmp?: Comparator<T>): T

  • Pushes value onto the heap, then pops to return the minimum element in the heap.

    This combined action runs faster than a push followed by a pop.

    This may return the value that was to be added, leaving the heap unchanged. If this is not the intended use, consider using heapreplace.

    see

    heapreplace

    Type parameters

    • T

    Parameters

    Returns T

heapreplace

  • heapreplace<T>(heap: T[], value: T, cmp?: Comparator<T>): T | undefined

  • Pops the minimum element from the heap and then pushes value onto the heap.

    Faster than a pop followed by a push.

    The returned element may be larger than the value added. If this is not desired, consider using heappushpop instead.

    see

    heappushpop

    Type parameters

    • T

    Parameters

    Returns T | undefined

useHeap

  • useHeap<T>(compare: Comparator<T>): { heapify: any; heappop: any; heappush: any; heappushpop: any; heapreplace: any }

  • Provides a wrapper for the heap methods in this module to set the compare method.

    Useful for defining a max-heap, or a heap that compares numbers by their value instead of their string representation.

    This functionality can be obtained by instead explicitly stating the custom compare method every time, but that can become quite verbose, and cause bugs if omitted.

    example
    // Normal heapify:
// Puts 10 ahead of 5 because it compares elements by their string
// representation.
heapify([100, 10, 5, 50]) // [10, 100, 5, 50]

// Redefined heapify:
// The true min (5) is at the front.
const { heapify } = useDefaultCompare((a, b) => a - b)
heapify([100, 10, 5, 50]) // [5, 10, 100, 50]

    Type parameters

    • T

    Parameters

    Returns { heapify: any; heappop: any; heappush: any; heappushpop: any; heapreplace: any }

    • heapify: function
      • heapify(arr: T[]): void
    • heappop: function
      • heappop(heap: T[]): undefined | T

      • Parameters

        • heap: T[]

        Returns undefined | T

    • heappush: function
      • heappush(heap: T[], value: T): void

      • Parameters

        • heap: T[]
        • value: T

        Returns void

    • heappushpop: function
      • heappushpop(heap: T[], value: T): T

      • Parameters

        • heap: T[]
        • value: T

        Returns T

    • heapreplace: function
      • heapreplace(heap: T[], value: T): undefined | T

      • Parameters

        • heap: T[]
        • value: T

        Returns undefined | T

Generated using TypeDoc