Heap-based Priority queue implementation on typescript for leetcode 973

kClosestPoints.ts

interface Node<T> {
    key: number;
    value: T;
}

class PriorityQueue<T> {
    heap: Node<T>[];

    constructor() {
        this.heap = [];
    }

    parent(index: number) {
        return Math.floor((index - 1) / 2);
    }

    leftChild(index: number) {
        return 2 * index + 1;
    }

    rightChild(index: number) {
        return 2 * index + 2;
    }

    hasLeft(index: number) {
        return this.leftChild(index) < this.heap.length;
    }

    hasRight(index: number) {
        return this.rightChild(index) < this.heap.length;
    }

    swap(a: number, b: number): void {
        const temp = this.heap[a];
        this.heap[a] = this.heap[b];
        this.heap[b] = temp;
    }

    insert(priority: number, item: T): void {
        this.heap.push({ key: priority, value: item });

        let i = this.heap.length - 1;

        while (i > 0) {
            const pIndex = this.parent(i);

            if (this.heap[pIndex].key < this.heap[i].key) break;
            this.swap(pIndex, i);

            i = pIndex;
        }
    }

    pop(): T {
        this.swap(0, this.heap.length - 1);
        const item = this.heap.pop() as Node<T>;

        // Order heap
        let current = 0;
        while (this.hasLeft(current)) {
            let smallestChild = this.hasRight(current)
                && this.heap[this.rightChild(current)].key < this.heap[this.leftChild(current)].key
                ? this.rightChild(current)
                : this.leftChild(current);
            
            if (this.heap[smallestChild].key > this.heap[current].key) break;

            this.swap(current, smallestChild);

            current = smallestChild;
        }

        return item.value;
    }
}

type Point = [x: number, y: number];

function getEuclidianDistance(point: Point): number {
    // In this case get closest to (0, 0)
    // Since I just need to compare distances, I don't need to get the sqrt
    return point[0] ** 2 + point[1] ** 2;
}

function kClosest(points: number[][], k: number): number[][] {
    const queue = new PriorityQueue<number[]>();

    points.forEach((point) => {
        queue.insert(getEuclidianDistance(point as Point), point);
    });

    const kClosest: number[][] = [];
    for (let i = 0; i < k; i++) {
        kClosest.push(queue.pop());
    }

    return kClosest;
};

export default kClosest;