Skip to content

Instantly share code, notes, and snippets.

@iplus26
Last active July 28, 2021 14:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save iplus26/f5b5df626f5248eea6cfb566a8b5636d to your computer and use it in GitHub Desktop.
Save iplus26/f5b5df626f5248eea6cfb566a8b5636d to your computer and use it in GitHub Desktop.
Heap implementation using TypeScript
class MinHeap {
readonly nodes: number[];
constructor(private size: number) {
this.nodes = [null];
}
getMin(): number {
return this.nodes[1];
}
insert(val: number) {
this.nodes.push(val);
this.sort();
}
pop(): number {
if (this.nodes.length === 0) {
return void 0;
}
if (this.nodes.length === 1) {
return this.nodes.pop();
}
// swap the first node and the last node
;[this.nodes[0], this.nodes[this.nodes.length - 1]] = [this.nodes[this.nodes.length - 1], this.nodes[0]];
const last = this.nodes.pop();
this.sort();
return last;
}
private sort() {
if (this.nodes.length > 2) {
let ptr = this.nodes.length - 1;
while(ptr >= 1) {
let parent = Math.floor(ptr/2);
if (ptr !== parent && this.nodes[ptr] < this.nodes[parent]) {
[this.nodes[ptr], this.nodes[parent]] = [this.nodes[parent], this.nodes[ptr]];
}
--ptr;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment