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.