The class supports two main operations: insert and remove. When inserting a new value, it's first added to the end of the array, and then "bubbled up" through the heap until it reaches its correct position. This process (heapifyUp) involves comparing the new value with its parent and swapping them if the parent is smaller, continuing until either the root is reached or the heap property is satisfied. The remove operation, which always removes the maximum value (the root), is more complex. It takes the root value, replaces it with the last element in the heap, and then "bubbles down" this element (heapifyDown) by repeatedly swapping it with its larger child until it reaches its correct position. This ensures that after any operation, the largest value always remains at the root, giving us O(1) access to the maximum value and O(log n) time for insertions and removals.
class MaxHeap {
public heap: number[] = [];
insert(val: number): void {
this.heap.push(val);
if (this.heap.length > 0) this.heapifyUp(this.heap.length - 1);
// Heapify up starting from the last element
}
private heapifyUp(nodeIndex: number): void {
if (nodeIndex == 0) return;
const nodeValue = this.heap[nodeIndex];
const parentIndex = Math.floor((nodeIndex - 1) / 2);
const parentValue = this.heap[parentIndex];
// In node value is higher than parent value, we need to propogate this (node) value up.
if (nodeValue > parentValue) {
[this.heap[nodeIndex], this.heap[parentIndex]] = [
this.heap[parentIndex],
this.heap[nodeIndex]
];
this.heapifyUp(parentIndex);
}
}
remove(): number {
if (this.heap.length == 0) return -1;
if (this.heap.length == 1) return this.heap.pop() as number;
const top = this.heap[0];
const last = this.heap.pop() as number;
this.heap[0] = last;
this.heapifyDown(0);
return top;
}
private heapifyDown(nodeIndex: number): void {
// Reached end of the heap
if (nodeIndex == this.heap.length - 1) return;
const nodeValue = this.heap[nodeIndex];
let leftChildIndex = Math.floor(nodeIndex * 2 + 1);
let rightChildIndex = Math.floor(nodeIndex * 2 + 2);
const leftChildValue = this.heap[leftChildIndex];
const rightChildValue = this.heap[rightChildIndex];
const indexToSwap = rightChildValue >= leftChildValue ? rightChildIndex : leftChildIndex;
if (this.heap[indexToSwap] > nodeValue) {
[this.heap[indexToSwap], this.heap[nodeIndex]] = [
this.heap[nodeIndex],
this.heap[indexToSwap]
];
this.heapifyDown(indexToSwap);
return;
}
}
}
export { MaxHeap };
import { MaxHeap } from './max_heap';
describe('Insert', () => {
test('Basic insert', () => {
const mh = new MaxHeap();
mh.insert(10);
expect(mh.heap).toStrictEqual([10]);
});
test('Basic sorting', () => {
const mh = new MaxHeap();
mh.insert(10);
mh.insert(100);
expect(mh.heap).toStrictEqual([100, 10]);
});
test('Insert with many values', () => {
const mh = new MaxHeap();
[10, 5, 2, 1, 100].forEach((num) => mh.insert(num));
expect(mh.heap).toStrictEqual([100, 10, 2, 1, 5]);
});
});
describe('Remove', () => {
test('Basic scenario', () => {
const mh = new MaxHeap();
mh.insert(10);
mh.remove();
expect(mh.heap).toStrictEqual([]);
});
test('Remove all values', () => {
const mh = new MaxHeap();
[10, 5, 2, 1, 100].forEach((num) => mh.insert(num));
[10, 5, 2, 1, 100].forEach((_) => mh.remove());
expect(mh.heap).toStrictEqual([]);
});
test('Remove one and resort', () => {
const mh = new MaxHeap();
[100, 40, 70, 10, 5, 2, 25, 1].forEach((num) => mh.insert(num));
mh.remove();
expect(mh.heap).toStrictEqual([70, 40, 25, 10, 5, 2, 1]);
});
test('Leetcode', () => {
const mh = new MaxHeap();
[1, 2, 3, 4, 5, 6, 7].forEach((num) => mh.insert(num));
const sortedMax = [1, 2, 3, 4, 5, 6, 7].map((_) => {
return mh.remove();
});
expect(sortedMax).toStrictEqual([7, 6, 5, 4, 3, 2, 1]);
});
test('Leetcode with duplicates', () => {
const mh = new MaxHeap();
[1, 4, 5, 1, 3, 4, 2, 6].forEach((num) => mh.insert(num));
const sortedMax = [1, 4, 5, 1, 3, 4, 2, 6].map((_) => {
return mh.remove();
});
expect(sortedMax).toStrictEqual([6, 5, 4, 4, 3, 2, 1, 1]);
});
});
class MinHeap {
public heap: number[] = [];
insert(val: number): void {
this.heap.push(val);
if (this.heap.length > 0) this.heapifyUp(this.heap.length - 1);
// Heapify up starting from the last element
}
private heapifyUp(nodeIndex: number): void {
if (nodeIndex == 0) return;
const nodeValue = this.heap[nodeIndex];
const parentIndex = Math.floor((nodeIndex - 1) / 2);
const parentValue = this.heap[parentIndex];
// In node value is higher than parent value, we need to propogate this (node) value up.
if (nodeValue < parentValue) {
[this.heap[nodeIndex], this.heap[parentIndex]] = [
this.heap[parentIndex],
this.heap[nodeIndex]
];
this.heapifyUp(parentIndex);
}
}
remove(): number {
if (this.heap.length == 0) return -1;
if (this.heap.length == 1) return this.heap.pop() as number;
const top = this.heap[0];
const last = this.heap.pop() as number;
this.heap[0] = last;
this.heapifyDown(0);
return top;
}
private heapifyDown(nodeIndex: number): void {
// Reached end of the heap
if (nodeIndex == this.heap.length - 1) return;
const nodeValue = this.heap[nodeIndex];
let leftChildIndex = Math.floor(nodeIndex * 2 + 1);
let rightChildIndex = Math.floor(nodeIndex * 2 + 2);
const leftChildValue = this.heap[leftChildIndex];
const rightChildValue = this.heap[rightChildIndex];
const indexToSwitch = rightChildValue <= leftChildValue ? rightChildIndex : leftChildIndex;
if (this.heap[indexToSwitch] < nodeValue) {
[this.heap[indexToSwitch], this.heap[nodeIndex]] = [
this.heap[nodeIndex],
this.heap[indexToSwitch]
];
this.heapifyDown(indexToSwitch);
return;
}
}
}
export { MinHeap };
import { MinHeap } from './min_heap';
describe('Insert', () => {
test('Basic insert', () => {
const mh = new MinHeap();
mh.insert(10);
expect(mh.heap).toStrictEqual([10]);
});
test('Basic sorting', () => {
const mh = new MinHeap();
mh.insert(10);
mh.insert(100);
expect(mh.heap).toStrictEqual([10, 100]);
});
test('Insert with many values', () => {
const mh = new MinHeap();
[10, 5, 2, 1, 100].forEach((num) => mh.insert(num));
expect(mh.heap).toStrictEqual([1, 2, 5, 10, 100]);
});
});
describe('Remove', () => {
test('Basic scenario', () => {
const mh = new MinHeap();
mh.insert(10);
mh.remove();
expect(mh.heap).toStrictEqual([]);
});
test('Remove all values', () => {
const mh = new MinHeap();
[10, 5, 2, 1, 100].forEach((num) => mh.insert(num));
[10, 5, 2, 1, 100].forEach((_) => mh.remove());
expect(mh.heap).toStrictEqual([]);
});
test('Remove one and resort', () => {
const mh = new MinHeap();
[100, 40, 70, 10, 5, 2, 25, 1].forEach((num) => mh.insert(num));
mh.remove();
expect(mh.heap).toStrictEqual([2, 10, 5, 100, 40, 70, 25]);
});
test('Leetcode', () => {
const mh = new MinHeap();
[1, 2, 3, 4, 5, 6, 7].forEach((num) => mh.insert(num));
const sortedMax = [1, 2, 3, 4, 5, 6, 7].map((_) => {
return mh.remove();
});
expect(sortedMax).toStrictEqual([1, 2, 3, 4, 5, 6, 7]);
});
test('Leetcode with duplicates', () => {
const mh = new MinHeap();
[1, 4, 5, 1, 3, 4, 2, 6].forEach((num) => mh.insert(num));
const sortedMax = [1, 4, 5, 1, 3, 4, 2, 6].map((_) => {
return mh.remove();
});
expect(sortedMax).toStrictEqual([1, 1, 2, 3, 4, 4, 5, 6]);
});
});