Top K Frequent Words Heap Solution [WIP]

simple_hash_soln.js

var topKFrequent = function(words, k, frequency = {}) {
    words.forEach(word => frequency[word] = frequency[word] + 1 || 1);
    
    return Object.keys(frequency).sort((left, right) => {
        const freqDiff = frequency[right] - frequency[left];
        return freqDiff === 0 ? left.localeCompare(right) : freqDiff;
    }).slice(0, k);
};

wip_frequency_heap.js

/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 */

class FreqHeap {
    constructor () {
        this.heap = [];
        this.counts = {};
        this.position = {}
    }
    
    add (word) {
        if (word in this.counts) {
            this.counts[word]++;
        } else {
            this.counts[word] = 1;
            this.position[word] = this.heap.length;
            this.heap.push(word);
        }
        
        this.bubbleUp(this.position[word]);
    }
    
    bubbleUp (index) {
        index = index == null ? this.heap.length - 1 : index;
        if (index === 0) return;
        
        const parentIndex = Math.floor(index / 2);
        
        const currentWord = this.heap[index];
        const parentWord = this.heap[parentIndex];
        const currentValue = this.counts[currentWord];
        const parentValue = this.counts[parentWord];
        
        const valueUnordered = currentValue > parentValue;
        // To fix this, we need to keep it completely ordered.
        // Will potentially have to do a neighbouring check, followed with a bubble down
        const lexicallyUnordered = currentWord.localeCompare(parentWord) === -1;
        
        if (valueUnordered || valueUnordered && lexicallyUnordered) {
            this.heap[index] = parentWord;
            this.position[parentWord] = index;
            this.heap[parentIndex] = currentWord;
            this.position[currentWord] = parentIndex;
            
            this.bubbleUp(parentIndex);
        }
    }
    
    topK (k) {
        return this.heap.slice(0, k);
    }
}

var topKFrequent = function(words, k) {
    const freqHeap = new FreqHeap();
    words.forEach(word => freqHeap.add(word));
    console.log(freqHeap);
    return freqHeap.topK(k);
};