JavaScript O(n log k) time and O(k) space using min-heap


  • 0
    class Heap {
        constructor(comparator) {
            this.data = [];
            this.comparator = comparator || ((parent, child) => parent - child);
        }
    
        get size() {
            return this.data.length;
        }
    
        bubbleUp(c) {
            if (c === 0) return;
            const p = Math.floor((c + 1) / 2) - 1;
            if (this.comparator(this.data[p], this.data[c]) > 0) {
                [this.data[p], this.data[c]] = [this.data[c], this.data[p]];
            }
            this.bubbleUp(p);
        }
    
        bubbleDown(p) {
            const c = 2 * (p + 1) - 1;
            if (c >= this.data.length) return;
    
            const leftDelta = this.comparator(this.data[p], this.data[c]);
            const rightDelta = c + 1 >= this.data.length ? 0 : this.comparator(this.data[p], this.data[c + 1]);
            if (leftDelta <= 0 && rightDelta <= 0) return;
    
            const swapChildIndex = c + (leftDelta <= rightDelta);
            [this.data[p], this.data[swapChildIndex]] = [this.data[swapChildIndex], this.data[p]];
            this.bubbleDown(swapChildIndex);
        }
    
        add(val) {
            this.data.push(val);
            this.bubbleUp(this.data.length - 1);
        }
    
        poll() {
            if (this.size < 2) return this.data.pop();
            [this.data[0], this.data[this.size - 1]] = [this.data[this.size - 1], this.data[0]];
            const val = this.data.pop();
            this.bubbleDown(0);
            return val;
        }
    }
    
    var mergeKLists = function(lists) {
        if (!lists.length) return null;
        
        const minHeap = new Heap((parent, child) => parent.val - child.val);
        for (let node of lists) {
            if (node) minHeap.add(node);
        }
        
        const dummy = new ListNode();
        let tail = dummy;
        while (minHeap.size) {
            tail.next = minHeap.poll();
            tail = tail.next;
            if (tail.next) minHeap.add(tail.next);
        }
        
        return dummy.next;
    };
    

    This is O(n log k) time where n is the total number of nodes and k is the number of lists or the maximum size of the heap.

    JavaScript doesn't have built-in priority queuing, so we use a heap from scratch here. I'm considering writing a JS package to fill some of these holes for LeetCode use.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.