There are a big portion of coding interview questions that you have to solve using Heap
data structure.
Ugh🤢 JavaScript doesn't come with Heap
#
It's quite a disadvantage that we JavaScripter don't have Heap
battery in our toolbox,
so normally we go for alternatives listed below:
1. Import libraries #
For example, I often make use of this one: https://www.collectionsjs.com/heap
Issues:
- Interviewers don't allow you to do that
- If it's online coding test, chances are that you just can't do that.
2. Explain verbally #
You can tell interviewers that you're gonna use Heap
to solve this question and focus on the core algorithm. You should provide at least the interface of the Heap
you will use and briefly explain the time complexity of each operation.
Issues:
- Interviewers in turn ask you to implement a real
Heap
- You can't use this approach during online coding tests.
3. Implement the Heap
using sort
function #
For each push
and pop
to the Heap
, you can make use of the JavaScript's sort
function to adjust the array.
Issues:
- The time complexity of
sort
function isO(NlogN)
, so your algorithm may go over the time limitation.
4. Implement the real Heap
on your own #
Although it's still a half-baked version, it follows how a real Heap
would work under the hood. As a result, the time complexity for push
and pop
are O(logN)
and you definitely can pass the time limitation of the given coding questions.
Issues:
- It takes time to implement your own
Heap
.
5. Use Python
instead #
😳😳😳
I believe people would feel more comfortable solving coding interview questions with the programming language they use for daily works.
Each option mentioned above can be a valid one depending on the situation. What we can do to prepare is to mitigate the impact of issues for each option. It turns out the only thing we can make more efforts is to master yourself in implementing your own Heap
faster, so that's what I do. The below is the implementation I always use, check it out!
My implementation #
class Heap {
constructor(compare) {
this.compare = compare;
this.arr = [];
}
get length() {
return this.arr.length;
}
peek() {
return this.arr.length > 0 ? this.arr[0] : null;
}
push(node) {
this.arr.push(node);
this.float(this.arr.length - 1);
}
// Brings a node up until its parent is greater
// (or smaller, depending on compare function) than it
float(index) {
const childNode = this.arr[index];
while (index > 0) {
// Compute the parent index (childIndex = parentIndex * 2 + 1 || parentIndex * 2 + 2)
const parentIndex = Math.floor((index - 1) / 2);
const parentNode = this.arr[parentIndex];
if (this.compare(childNode, parentNode) > 0) {
[this.arr[index], this.arr[parentIndex]] = [
this.arr[parentIndex],
this.arr[index],
];
index = parentIndex;
} else {
break;
}
}
}
pop() {
if (this.length === 0) return null;
if (this.length === 1) return this.arr.pop();
// The top node will be return
const currTop = this.arr[0];
// Get the new top node from the end of the array
// because if we use the second top one, it might
// mess up the order of the tree
const newTop = this.arr.pop();
this.arr[0] = newTop;
if (this.arr.length > 1) {
this.sink(0);
}
return currTop;
}
// Brings a node down until its children are both less than
// (or greater than, depending on compare function) than it
sink(index) {
const heapSize = this.arr.length;
while (true) {
const leftChildIndex = index * 2 + 1;
const rightChildIndex = index * 2 + 2;
let swapIndex = index, needsSwap = false;
let leftChildNode, rightChildNode;
if (leftChildIndex < heapSize) {
leftChildNode = this.arr[leftChildIndex];
const parentNode = this.arr[index];
if (this.compare(leftChildNode, parentNode) > 0) {
swapIndex = leftChildIndex;
needsSwap = true;
}
}
if (rightChildIndex < heapSize) {
rightChildNode = this.arr[rightChildIndex];
const swapNode = this.arr[swapIndex];
if (
this.compare(rightChildNode, swapNode) >
0
) {
swapIndex = rightChildIndex;
needsSwap = true;
}
}
if (needsSwap) {
[this.arr[index], this.arr[swapIndex]] = [
this.arr[swapIndex],
this.arr[index],
];
index = swapIndex;
// continue sinking
} else {
// Both children are greater than (or less than) the parent node
break;
}
}
}
}
To test your own Heap
implementation, you can try:
const maxHeap = new Heap((a, b) => a - b);
maxHeap.push(2);
console.log(maxHeap.peek()); // 2
maxHeap.push(8);
console.log(maxHeap.peek()); // 8
maxHeap.push(1);
console.log(maxHeap.pop()); // 8
console.log(maxHeap.peek()); // 2
That's it 👨💻! JavaScripters are not second-class citizens anymore 😄!
🙏🙏🙏 Since you've made it this far, sharing this article on your favorite social media network would be highly appreciated 💖! For feedback, please ping me on Twitter.
Published