1 class MinHeap {
 2   constructor(){
 3     this.heap = [];
 4   }
 5   swap(i1, i2){
 6     const temp = this.heap[i1];
 7     this.heap[i1] = this.heap[i2];
 8     this.heap[i2] = temp;
 9   }
10   getParentIndex(i){  //获取父节点的值
11     return (i-1) >> 1;  //二进制右移相当于除以2
12   }
13   getLeftIndex(i) {  //获取左结点
14     return i * 2 + 1;
15   }
16   getRightIndex(i) {  //获取右结点
17     return i * 2 + 2;
18   }
19 
20   shiftUp(index){   //需要让父节点不断小于它的子节点
21     if(index == 0){ return; }  //如果已经是根结点了就不用找了
22     const parentIndex = this.getParentIndex(index);
23     if(this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value){
24       this.swap(parentIndex, index);  //如果父节点的值大于子节点则进行交换
25       this.shiftUp(parentIndex)
26     }
27   }
28   insert(value){  //插入，添加的方法
29     this.heap.push(value);
30     this.shiftUp(this.heap.length - 1);  //shiftUp就是上移操作，接收参数是上移时的下标
31   }
32   shiftDown(index){  //下移节点，直到子节点都大于当前节点的值
33     // 需要获取它的左右子节点
34     const leftIndex = this.getLeftIndex(index);
35     const rightIndex = this.getRightIndex(index);
36     if(this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value){  //小顶堆，父节点小于子节点
37       this.swap(leftIndex, index);
38       this.shiftDown(leftIndex);  //迭代，直到找到合适的位置
39     }
40     if(this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value){  //小顶堆，父节点小于子节点
41       this.swap(rightIndex, index);
42       this.shiftDown(rightIndex);  //迭代，直到找到合适的位置
43     }
44   }
45 
46   pop(){   //下移方法
47     this.heap[0] = this.heap.pop();  // 把数组的最后一位转移到头部，相当于变相删除堆顶
48     this.shiftDown(0);  //传什么下标，就对那个进行下移操作
49   }
50   peek(){ //获取堆顶，返回数组的头部
51     return this.heap[0];
52   }
53   size(){  // 获取堆的大小
54     return this.heap.length;
55   }
56 }
57 /**
58  * @param {number[]} nums
59  * @param {number} k
60  * @return {number[]}
61  */
62 var topKFrequent = function(nums, k) {
63     const map = new Map();
64     nums.forEach(n=>{
65         map.set(n, map.has(n)?map.get(n)+1:1);
66     })
67     const h = new MinHeap();
68     map.forEach((value, key) => {
69         h.insert({ value,key });
70         if(h.size() > k){  //超出堆的大小之后，就弹出来
71             h.pop()  //把堆顶的删除，最小的元素在堆顶
72         }
73     });
74     return h.heap.map( a => a.key)
75 };