My two cents:
- Each push and pop requires a rearrangement of the existing elements, it's almost like the priority queue is a living organism which evolves / devolves it self to maintain the order of the elements.
Swap, BubbleUp, & BubbleDown are the methods doing the main lifting. Here, swap is the simple swap operation
const temp: T = this.heap[i];
this.heap[i] = this.heap[j];
this.heap[j] = tempThe
this.comparedependency injection is the soul of the code here. It is the same deciding factor which is used in sorting elements in an array.number < 0,number = 0&number > 0
where number is the result of a-b or b-a.
bubbleUp and bubbleDown ensure the rearrangement which is required to maintain the order of the elements,
bubbleDown refers to the Pop operation, and bubbleUp refers to the push operation. This is because how they are implemented in the custom heap inside the CustomPriorityQueue class.
Complexity
- Time complexity: O(N * log(N)); explanation : Push, Pop has log(N) and Stones array traversal has N.
- Space complexity: O(N) for additional priority queue.
Code
function lastStoneWeight(stones: number[]): number {
const PQ = new CustomPriorityQueue<number>((a, b) => b-a);
for (let i of stones) {
PQ.push(i);
}
while(PQ.size() > 1){
const y: number = PQ.pop();
const x: number = PQ.pop();
if(y>x){
PQ.push(y-x);
}
}
// console.log(PQ);
return PQ.isEmpty() ? 0 : PQ.peak();
};
class CustomPriorityQueue<T> {
private heap: T[] = [];
private compare: ((a: T, b: T) => number);
constructor(compare: (a: T, b: T) => number) {
this.compare = compare
// this.heap = [];
}
public size(): number {
return this.heap.length
}
public isEmpty(): boolean {
return this.size() === 0;
}
public peak(): T | undefined {
return this.heap[0]
}
private swap(i: number, j: number): void {
const temp: T = this.heap[i];
this.heap[i] = this.heap[j];
this.heap[j] = temp
}
public push(value: T): void {
this.heap.push(value);
this.bubbleUp(this.size() - 1);
}
private bubbleUp(index: number): void {
while (index > 0) {
let parentIndex: number = Math.floor((index - 1) / 2);
if (this.compare(this.heap[parentIndex], this.heap[index]) < 0) break;
this.swap(parentIndex, index);
index = parentIndex
}
}
public pop(): T | undefined {
if (this.isEmpty()) return undefined;
const top: T = this.heap[0];
const bottom: T = this.heap.pop();
if (!this.isEmpty() && bottom !== undefined) {
this.heap[0] = bottom;
this.bubbleDown(0);
}
return top;
}
private bubbleDown(index: number): void {
const length: number = this.size();
while (true) {
let leftChildIndex: number = 2 * index + 1;
let rightChildIndex: number = 2 * index + 2
let indexOfSmallestOrLargest: number = index;
if (leftChildIndex < length && this.compare(this.heap[leftChildIndex], this.heap[indexOfSmallestOrLargest]) < 0) {
indexOfSmallestOrLargest = leftChildIndex;
}
if (rightChildIndex < length && this.compare(this.heap[rightChildIndex], this.heap[indexOfSmallestOrLargest]) < 0) {
indexOfSmallestOrLargest = rightChildIndex;
}
if (indexOfSmallestOrLargest === index) break;
this.swap(index, indexOfSmallestOrLargest);
index = indexOfSmallestOrLargest
}
}
}