Last active
February 3, 2022 03:15
-
-
Save Phryxia/cb020aa226d6276c86c712da315581a4 to your computer and use it in GitHub Desktop.
Simple Heap implementation for JavaScript/TypeScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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 returnundefined
instead of throwing error under circumstances.