Skip to content

Instantly share code, notes, and snippets.

@Phryxia
Last active February 3, 2022 03:15
Show Gist options
  • Save Phryxia/cb020aa226d6276c86c712da315581a4 to your computer and use it in GitHub Desktop.
Save Phryxia/cb020aa226d6276c86c712da315581a4 to your computer and use it in GitHub Desktop.
Simple Heap implementation for JavaScript/TypeScript
class Heap {
constructor(comparator) {
this.data = []
this.comparator = comparator
}
push(value) {
this.data.push(value)
this.siftUp(this.size() - 1)
return value
}
pop() {
if (this.size() <= 0) throw Error('heap is empty')
const result = this.data[0]
this.swap(0, this.size() - 1)
this.data.pop()
this.siftDown(0)
return result
}
top() {
if (this.size() <= 0) throw Error('heap is empty')
return this.data[0]
}
size() {
return this.data.length
}
siftUp(index) {
if (index <= 0) return
const pIndex = Math.floor((index - 1) / 2)
if (this.comparator(this.data[pIndex], this.data[index]) >= 0) return
this.swap(index, pIndex)
this.siftUp(pIndex)
}
siftDown(index) {
if (2 * index + 1 >= this.size()) return
const superior =
2 * index + 2 >= this.size() ||
this.comparator(this.data[2 * index + 1], this.data[2 * index + 2]) >= 0
? 2 * index + 1
: 2 * index + 2
if (this.comparator(this.data[index], this.data[superior]) >= 0) return
this.swap(index, superior)
this.siftDown(superior)
}
swap(a, b) {
const temp = this.data[a]
this.data[a] = this.data[b]
this.data[b] = temp
}
}
class Heap<T> {
private data: T[] = []
public constructor(private comparator: (a: T, b: T) => number) {}
public push(value: T): T {
this.data.push(value)
this.siftUp(this.size() - 1)
return value
}
public pop(): T {
if (this.size() <= 0) throw Error('heap is empty')
const result = this.data[0]
this.swap(0, this.size() - 1)
this.data.pop()
this.siftDown(0)
return result
}
public top(): T {
if (this.size() <= 0) throw Error('heap is empty')
return this.data[0]
}
public size(): number {
return this.data.length
}
private siftUp(index: number): void {
if (index <= 0) return
const pIndex = Math.floor((index - 1) / 2)
if (this.comparator(this.data[pIndex], this.data[index]) >= 0) return
this.swap(index, pIndex)
this.siftUp(pIndex)
}
private siftDown(index: number): void {
if (2 * index + 1 >= this.size()) return
const superior =
2 * index + 2 >= this.size() ||
this.comparator(this.data[2 * index + 1], this.data[2 * index + 2]) >= 0
? 2 * index + 1
: 2 * index + 2
if (this.comparator(this.data[index], this.data[superior]) >= 0) return
this.swap(index, superior)
this.siftDown(superior)
}
private swap(a: number, b: number): void {
const temp = this.data[a]
this.data[a] = this.data[b]
this.data[b] = temp
}
}
@Phryxia
Copy link
Author

Phryxia commented Feb 3, 2022

This works as max-heap with following natural comparator: (a, b) => a - b. Also this throws error when element is requested but there is nothing inside. You may return undefined instead of throwing error under circumstances.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment