A simple module to maintain a binary heap.
yarn add @shlappas/heap
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.heappush
, heappop
, heappushpop
, or heapreplace
achieves
the intended result. For more information, check out the
docs. Built with
typedoc
!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/heapq'
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 { useCompare } from '@shlappas/heapq'
const { heapify, heappop } = useCompare<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]
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
!*
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.
Generated using TypeDoc