堆的概念

堆是一种特殊的完全二叉树
所有节点都大于等于（最大堆）或小于等于（最小堆）它的子节点

JS中常用数组表示堆
广度优先遍历填到数组中
任意节点的左侧子节点的位置是2 * index + 1
任意节点的右侧子节点的位置是2 * index + 2
任意节点的父节点的位置是(index - 1) / 2

应用

堆能高效快速的找出最大值和最小值，时间复杂度：O(1)
找出第K个最大（小）元素

第K个最大（小）元素

构建一个最小（大）堆，并将元素一次插入堆中
当堆的容量超过K，就删除堆顶
插入结束后，堆顶就是第K个最大元素

js实现最小堆

步骤

在类里，申明一个数组，用来装元素
主要方法：插入、删除堆顶，获取堆顶，获取堆大小
```
class minHeap {
  constructor() {
      this.heap = []
  }
}
```
插入
将值插入堆的底部，即数组的尾部
然后上移：将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值

大小为k的堆中插入元素的时间复杂度为O(logk) ```javascript class MinHeap { constructor() {

  this.heap = []

}

// 交换两个元素

swap(n1, n2) {

  const temp = this.heap[n1]
  this.heap[n1] = this.heap[n2]
  this.heap[n2] = temp

}

// 获取父节点的值

getParentIndex(index) {

  // 除以2取商
  // return Math.floor((index - 1) / 2)
  return (index - 1) >> 1

}

// 上移逻辑

shiftUp(index) {

    // 当遇到堆顶则停止上移
  if(index === 0) return
  const parentIndex = this.getParentIndex(index)
  // 利用父节点的值永远小于子节点这个特性（最小堆）
  if(this.heap[parentIndex] > this.heap[index]) {
        // 交换
      this.swap(parentIndex, index)
        // 上移
      this.shiftUp(parentIndex)
  }

}

// 插入

insert(value) {

    // 插入到堆底
  this.heap.push(value)
  this.shiftUp(this.heap.length -1)

} }

const heap = new MinHeap() heap.insert(3) heap.insert(2) heap.insert(1) heap.insert(5) heap.insert(8)

<a name="wQAAg"></a>
### 删除堆顶
- 用数组尾部的元素替换堆顶并删除数组尾部的元素（直接删除堆顶会破坏堆结构）
- 然后下移：将新的堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶
- 大小为K的堆中删除堆顶的时间复杂度为O(logk)
```javascript
class MinHeap {
    constructor() {
        this.heap = []
    }
    swap(n1, n2) {
        const temp = this.heap[n1]
        this.heap[n1] = this.heap[n2]
        this.heap[n2] = temp
    }
    getParentIndex(index) {
        // 除以2取商
        // return Math.floor((index - 1) / 2)
        return (index - 1) >> 1
    }
      // 获取左节点
    getLeftIndex(index) {
        return (index * 2) + 1
    }
      // 获取右节点
    getRightIndex(index) {
        return (index * 2) + 2
    }
    shiftUp(index) {
        if(index === 0) return
        const parentIndex = this.getParentIndex(index)
        if(this.heap[parentIndex] > this.heap[index]) {
            this.swap(parentIndex, index)
            this.shiftUp(parentIndex)
        }
    }
      // 下移逻辑
    shiftDown(index) {
        const leftIndex = this.getLeftIndex(index)
        const rightIndex = this.getRightIndex(index)
        // 利用子节点的值永远大于父节点（最小堆）
        if(this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index)
            this.shiftDown(leftIndex)
        }
        if(this.heap[rightIndex] < this.heap[index]) {
            this.swap(rightIndex, index)
            this.shiftDown(rightIndex)
        }
    }
    insert(value) {
        this.heap.push(value)
        this.shiftUp(this.heap.length -1)
    }
      // 删除堆顶
    pop(){
        this.heap[0] = this.heap.pop()
        this.shiftDown(0)
    }
}
const heap = new MinHeap()
heap.insert(3)
heap.insert(2)
heap.insert(1)
heap.insert(5)
heap.insert(8)
heap.pop()

获取堆顶和堆的大小

获取堆顶：返回数组头部
获取堆的大小：返回数组的长度
题目
1.数组中的第K个最大元素 - 215
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

思路：

看到第K个最大元素
考虑使用最小堆来解决

解题步骤：

构建一个最小堆，把数组中的元素插入堆中
当堆的容量超过K，就删除堆顶

插入结束后，堆顶就是第K个最大元素 ```javascript class MinHeap { constructor() {

  this.heap = []

} swap(n1, n2) {

  const temp = this.heap[n1]
  this.heap[n1] = this.heap[n2]
  this.heap[n2] = temp

} getParentIndex(index) {

  // 除以2取商
  // return Math.floor((index - 1) / 2)
  return (index - 1) >> 1

} getLeftIndex(index) {

  // 除以2取商
  // return Math.floor((index - 1) / 2)
  return (index * 2) + 1

} getRightIndex(index) {

  // 除以2取商
  // return Math.floor((index - 1) / 2)
  return (index * 2) + 2

} shiftUp(index) {

  if(index === 0) return
  const parentIndex = this.getParentIndex(index)
  if(this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
  }

} shiftDown(index) {

  const leftIndex = this.getLeftIndex(index)
  const rightIndex = this.getRightIndex(index)
  if(this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
  }
  if(this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
  }

} insert(value) {

  this.heap.push(value)
  this.shiftUp(this.heap.length -1)

} pop(){

  this.heap[0] = this.heap.pop()
  this.shiftDown(0)

} peek() {

  return this.heap[0]

} size() {

  return this.heap.length

} }

/**

@param {number[]} nums
@param {number} k
@return {number} */ var findKthLargest = function(nums, k) { // 构建一个最小堆 const minHeap = new MinHeap() nums.forEach(item => {
```
   // 将数组中的元素插入到堆中
 minHeap.insert(item)
   // 当堆的大小超过K
 if(minHeap.size() > k) {
       // 就删除堆顶元素
     minHeap.pop()
 }
```
}) // 返回堆顶，因为长度为k，堆顶是堆中最小值，所以堆顶就是第K大的元素 return minHeap.peek()

};

<a name="oWX1O"></a>
## 2.前K个高频要素 - 347
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:<br />输入: nums = [1,1,1,2,2,3], k = 2<br />输出: [1,2]
示例 2:<br />输入: nums = [1], k = 1<br />输出: [1]
提示：
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
思路1（暴力统计法-时间复杂度不符合）：
- 统计nums中数字出现的频率
- 降序排列
- 取出前k个元素
解题步骤1：
- 利用map统计频率
- 对map按照频率降序排列
- 返回前k个元素
```javascript
/**
 * 暴力统计法（时间复杂度不符合）
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
      // 利用map统计元素出现的频率
    const map = new Map()
    nums.forEach(n => {
        map.set(n, map.has(n) ? map.get(n) + 1 : 1)
    })
      // 对map按照频率进行排序
      // Array.sort()的时间复杂度最优为nlogn（快排）
    const list = Array.from(map).sort((a, b) => b[1] - a[1])
    // 返回数组中前k个元素
    return list.slice(0, k).map(n => n[0])
};

思路2（堆）:

建立一个最小堆
把元素以及频率插入到堆中，并按照频率进行排序
维持堆的大小永远为k

堆中前k个元素即为频率前k高的元素 ```javascript class MinHeap { constructor() {

  this.heap = []