347. top k high frequency elements heap sort + bucket sort +map

source ：347. front K High frequency elements

Give you an array of integers nums And an integer k , Please return to the frequency before k High element . You can press In any order Return to the answer .
Example :

• Input : nums = [1,1,1,2,2,3], k = 2
• Output : [1,2]

Solution 1 ：map+ Bucket sort

let topKFrequent = function(nums, k) {
    
    let map = new Map(), arr = [...new Set(nums)]
    nums.map((num) => {
    
        if(map.has(num)) map.set(num, map.get(num)+1)
        else map.set(num, 1)
    })
    
    //  If the number of elements is less than or equal to  k
    if(map.size <= k) {
    
        return [...map.keys()]
    }
    
    return bucketSort(map, k)
};

//  Bucket sort 
let bucketSort = (map, k) => {
    
    let arr = [], res = []
    map.forEach((value, key) => {
    
        //  Using mapping relationships （ Frequency of occurrence as a subscript ） Distribute data into buckets 
        if(!arr[value]) {
    
            arr[value] = [key]
        } else {
    
            //  This code block has not been executed 
            arr[value].push(key)
        }
    })
    // console.log('arr:', arr)
    // arr:  Two dimensional array 
    // （ Maximum frequency of occurrence +1） by arr Length of array , The array corresponding to the occurrence frequency not involved is empty 
    //  Traversal in reverse order to obtain the top with the highest frequency k Number 
    for(let i = arr.length - 1;i >= 0 && res.length < k;i--){
    
        if(arr[i]) {
    
            // console.log('arr[i]:', arr[i])
            res.push(...arr[i])
        }
	}
	return res
}

console.log(topKFrequent([1,1,1,1,1,2,2,3],2))

Solution 2 ：map+ Heap sort

let topKFrequent = function(nums, k) {
    
    let map = new Map(), heap = [,]
    nums.map((num) => {
    
        if(map.has(num)) map.set(num, map.get(num)+1)
        else map.set(num, 1)
    })
    
    //  If the number of elements is less than or equal to  k
    if(map.size <= k) {
    
        return [...map.keys()]
    }
    
    //  If the number of elements is greater than  k, Traverse map, Build a small top pile 
    let i = 0
    map.forEach((value, key) => {
    
        if(i < k) {
    
            //  Take before k Building pile ,  Insert heap 
            heap.push(key)
            //  Before the original establishment  k  Pile up 
            if(i === k-1) buildHeap(heap, map, k)
        } else if(map.get(heap[1]) < value) {
    
            //  Replace and heap 
            heap[1] = key
            //  Top down heap the first element 
            heapify(heap, map, k, 1)
        }
        i++
    })
    //  Delete heap The first element in 
    heap.shift()
    return heap
};

//  Build a pile in place , From back to front , Build a small top pile from top to bottom 
let buildHeap = (heap, map, k) => {
    
    if(k === 1) return
    //  Start with the last non leaf node , Top down stacking 
    for(let i = Math.floor(k/2); i>=1 ; i--) {
    
        heapify(heap, map, k, i)
    }
}

//  The heap, 
let heapify = (heap, map, k, i) => {
    
    //  Top down stacking 
    while(true) {
    
        let minIndex = i
        if(2*i <= k && map.get(heap[2*i]) < map.get(heap[i])) {
    
            minIndex = 2*i
        }
        if(2*i+1 <= k && map.get(heap[2*i+1]) < map.get(heap[minIndex])) {
    
            minIndex = 2*i+1
        }
        if(minIndex !== i) {
    
            swap(heap, i, minIndex)
            i = minIndex
        } else {
    
            break
        }
    }
}

//  In exchange for 
let swap = (arr, i , j) => {
    
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

console.log(topKFrequent([1,1,1,1,1,2,2,3],2))

Reference blog ：JS Implement heap sort 、 data structure ： Pile up （Heap）、JS Implement heap sort