1.html

<script>
/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 */
const swap = (arr, idx1, idx2) => {
  const temp = arr[idx1]
  arr[idx1] = arr[idx2]
  arr[idx2] = temp
}

class Heap {
  constructor (map) {
    this.arr = [] // 从下标1开始存储数据
    this.count = 0// 堆已经存储的数据个数
    map.forEach((val, key) => { 
      console.log(key, val)
      this.insert({ key, val })
    })
  }

  insert (data) {
    this.count++
    this.arr[this.count] = data
    let i = this.count
    // 把节点放在最后，对比当前节点与父节点的关系，如果不满足，则互换节点
    
    while ((i / 2 | 0) > 0) { // 自下往上堆化
      const { key: key1, val: val1 } = this.arr[i]
      const { key: key2, val: val2 } = this.arr[(i / 2 | 0)]
      if (val1 > val2 || (val1 === val2 && key1 < key2)) {
        swap(this.arr, i, (i / 2 | 0))
        i = i / 2 | 0
      } else {
        break
      }
    }
  }

  removeMax () {
    const heapify = (arr, n, i) => {
      while (true) { // 自上往下堆化
        let maxPos = i
        if (i*2 <= n && arr[i].val < arr[i*2].val) maxPos = i*2
        if (i*2+1 <= n && arr[maxPos].val < arr[i*2+1].val) maxPos = i*2+1
        if (maxPos == i) break
        swap(arr, i, maxPos)
        i = maxPos
      }
    }

    if (this.count === 1) return {} // 堆中没有数据
    const max = this.arr[1]
    this.arr[1] = this.arr[this.count]
    this.count--
    heapify(this.arr, this.count, 1)
    return max
  }

  printHeap () {
    return this.arr
  }
}

// 遍历一遍数组统计每个元素的频率，并将元素值key与出现的频率value保存到map中
const topKFrequent = (nums, k) => {
  const map = new Map()
  nums.forEach(num => {
    map.set(num, (map.get(num) || 0) + 1)
  })

  // 如果元素数量小于等于k
  if (map.size <= k) {
    return [...map.keys()]
  }

  // 如果元素数量大于k, 遍历map，将前k个数，构造一个小顶堆
  const heap = new Heap(map)
  console.log(map)
  console.log(heap)
  const result = []
  while (k > 0) {
    result.push(heap.removeMax().key)
    k--
  }
  return result
}

topKFrequent(["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], 3)
</script>