https://leetcode.com/problems/ugly-number-ii/

uglyNumber2.js

var nthUglyNumber = function(n) {
    
    const uglies = [1];
    const heap = new Heap((a, b) => a - b);
    heap.push(1);
    
    while(uglies.length < n){
        
        const lastUgly = uglies[uglies.length-1];

        heap.push(lastUgly*2);
        heap.push(lastUgly*3);
        heap.push(lastUgly*5);

        while(heap.peak() <= lastUgly) heap.pop(); // remove duplicates
        uglies.push(heap.pop());
    }
    
    return uglies.pop();
};


// https://github.com/RP-3/lc-data-structures
class Heap {
    constructor(comparator, maxSize = Infinity) {
        this.comparator = comparator;
        this.maxSize = maxSize;
        this.storage = [];
    }
    static heapify(array, comparator, maxSize = Infinity) {
        const result = new Heap(comparator, maxSize);
        result.storage = array;
        result.heapify();
        return result;
    }
    push(val) {
        this.storage.push(val);
        this.percolateUp(this.storage.length - 1);
        if (this.storage.length > this.maxSize)
            return this.pop();
        return null;
    }
    pop() {
        if (this.storage.length === 0)
            return null;
        if (this.storage.length === 1)
            return this.storage.pop();
        const tmp = this.storage[0];
        this.storage[0] = this.storage.pop();
        this.percolateDown(0);
        return tmp;
    }
    peak() {
        if (!this.storage.length)
            return null;
        return this.storage[0];
    }
    size() {
        return this.storage.length;
    }
    inOrder(parentIndex, childIndex) {
        return this.comparator(this.storage[parentIndex], this.storage[childIndex]) <= 0;
    }
    percolateUp(i) {
        let parentIndex = this.parentIndex(i);
        while (parentIndex >= 0 && parentIndex < i && !this.inOrder(parentIndex, i)) {
            const tmp = this.storage[parentIndex];
            this.storage[parentIndex] = this.storage[i];
            this.storage[i] = tmp;
            i = parentIndex;
            parentIndex = this.parentIndex(i);
        }
    }
    percolateDown(i) {
        let childIndex = this.highestPriorityChildIndex(i);
        while (childIndex !== null && !this.inOrder(i, childIndex)) {
            [this.storage[i], this.storage[childIndex]] = [this.storage[childIndex], this.storage[i]];
            i = childIndex;
            childIndex = this.highestPriorityChildIndex(i);
        }
    }
    highestPriorityChildIndex(parentIndex) {
        const leftChildIndex = this.leftChildIndex(parentIndex);
        const rightChildIndex = this.rightChildIndex(parentIndex);
        if (leftChildIndex >= this.storage.length)
            return null;
        if (rightChildIndex >= this.storage.length)
            return leftChildIndex;
        const leftChild = this.storage[leftChildIndex];
        const rightChild = this.storage[rightChildIndex];
        const comparison = this.comparator(leftChild, rightChild);
        return (comparison <= 0) ? leftChildIndex : rightChildIndex;
    }
    parentIndex(childIndex) {
        return Math.floor((childIndex - 1) / 2);
    }
    leftChildIndex(parentIndex) {
        return parentIndex * 2 + 1;
    }
    rightChildIndex(parentIndex) {
        return parentIndex * 2 + 2;
    }
    heapify() {
        if (!this.storage.length)
            return;
        let parentIndex = Math.floor((this.storage.length - 1 - 1) / 2);
        while (parentIndex >= 0)
            this.percolateDown(parentIndex--);
    }
}