Nauseating Pumpkin Mush

    @shlappas/heap
    TypeScript icon, indicating that this package has built-in type declarations

    1.0.5 • Public • Published

    npm version Build Status

    Heap

    A simple module to maintain a binary heap.

    Installation

    yarn add @shlappas/heap

    Usage

    Similar to the python heapq module, the actual datastructure is just a normal array!

    const heap = [9, 7, 6, 4, 1]
    heapify(heap) // now heap is a min-heap!

    Calling heapify makes sure that we can do the following:

    • heap[0] is the minimum element in the array.
    • Calling any of heappush, heappop, heappushpop, or heapreplace achieves the intended result. For more information, check out the docs. Built with typedoc!

    Default Compare

    In keeping with the builtin Array.prototype.sort() function, the default behaviour of the heap methods is to compare values based on their string representation.

    const heap = [10, 100, 5, 50]
    heapify(heap) // [10, 100, 5, 50], since '10' < '5' etc.

    If this is not intended, there are two options:

    • Pass a custom compare function to each individual call:

      import { heapify, heappop } from '@shlappas/heap'
      
      const compare = (a: number, b: number) => a - b
      
      const heap = [10, 100, 5, 50]
      
      heapify(heap, compare) // [5, 50, 10, 100]
      heappop(heap, compare) // 5 and the remaining heap is [10, 50, 100]
    • Redefine the heap methods with a fixed compare function:

      const { useHeap } from '@shlappas/heap'
      
      const { heapify, heappop } = useHeap<number>((a, b) => a - b)
      const heap = [10, 100, 5, 50]
      
      heapify(heap) // [5, 50, 10, 100]
      heappop(heap) // 5 and the remaining heap is [10, 50, 100]

    Examples

    N Largest

    We can find the n largest elements of an array*:

    function nLargest<T, N extends number>(arr: T[], n: N): Tuple<T, N> {
      const result: T[] = []
    
      for (let i = 0; i < n; i++) {
        result.push(arr[i])
      }
    
      heapify(result)
    
      for (let i = n; i < arr.length; i++) {
        heappushpop(result, arr[i])
      }
    
      return result as Tuple<T, N>
    }

    Shameless plug: For the Tuple type, consider using tuple-type!

    Merge

    We can merge a bunch of already sorted arrays*:

    function merge(compare, ...preSorted) {
      const result = []
    
      const status = [...zip(repeat(0), preSorted)]
    
      const { heapify, heappop, heapreplace } = useHeap(([i1, l1], [i2, l2]) => {
        return compare(l1[i1], l2[i2])
      })
    
      heapify(status)
    
      while (status.length) {
        const [idx, list] = status[0]
        result.append(list[idx])
        idx += 1
        if (idx === list.length) {
          heappop(status)
        } else {
          heapreplace(status, [idx, list])
        }
      }
    
      return result
    }

    Shameless Plug 2: Electric Boogaloo: For the zip, filter and repeat functions (along with some other nice tools for iterators), consider using @shlappas/itertools!

    * I reccomend not using these implementations verbatim; some heavy assumptions are made in the name of brevity. Check out examples for some safer implementations.

    Install

    npm i @shlappas/heap

    DownloadsWeekly Downloads

    2

    Version

    1.0.5

    License

    MIT

    Unpacked Size

    18.2 kB

    Total Files

    7

    Last publish

    Collaborators

    • shlappas