'MinHeap solution for LC 703 - Why doesn't mine work?
I've been working on leetcode #703, building my own min heap implementation in typescript. My solution passes 9/10 testcases, however I have no idea what is going on in the one that I am missing. I can't test it either, since the one it is failing has a large amount of add commands. Can someone look at the code and see if they can find a potential cause?
Here is the KthLargest class:
class KthLargest {
k: number;
heap: MinHeap;
constructor(k: number, nums: number[]) {
this.k = k;
this.heap = new MinHeap();
nums.forEach(element => {
this.heap.insert(element)
});
}
add(val: number): number {
if (val >= this.heap.root() || this.heap.size() < this.k) {
this.heap.insert(val);
}
while (this.heap.size() > this.k) {
this.heap.remove();
}
return this.heap.root();
}
}
Here is my min heap implementation:
class MinHeap {
heap: number[];
parent: (i: number) => number;
leftChild: (i: number) => number;
rightChild: (i: number) => number;
size: () => number;
root: () => number;
isLeaf: (i: number) => boolean;
constructor() {
this.heap = [];
this.parent = (i: number) => (Math.floor((i - 1) / 2));
this.leftChild = (i: number) => (2 * i + 1);
this.rightChild = (i: number) => (2 * i + 2);
this.size = () => this.heap.length;
this.root = () => this.heap[0];
this.isLeaf = (i: number) => { return ((i > (this.size() / 2)) && (i <= this.size())); }
}
heapify(i: number) {
if (!(this.isLeaf(i))) {
if (this.heap[i] > this.heap[this.leftChild(i)]
|| this.heap[i] > this.heap[this.rightChild(i)]) {
if (this.heap[this.leftChild(i)] < this.heap[this.rightChild(i)]) {
this.swap(i, this.leftChild(i));
this.heapify(this.leftChild(i));
} else {
this.swap(i, this.rightChild(i));
this.heapify(this.rightChild(i));
}
}
}
}
insert(val: number) {
let current: number = this.size();
this.heap.push(val);
while (this.heap[current] < this.heap[this.parent(current)]) {
this.swap(current, this.parent(current));
current = this.parent(current);
}
}
remove(): number {
let popped: number = this.heap[0];
this.heap.shift();
this.heapify(0);
return popped;
}
swap(index1: number, index2: number) {
[this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
}
}
Thank you to anyone who is willing to go through all of this.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
