和普通队列的区别

保证每次取出的元素优先级最高，优先级自己定义

最常用的场景

从杂乱无章的数据中顺序取出数据

本质

利用数组实现的完全二叉树，array[0] 有最高优先级，对于 array[i] 来说父结点为 i-1/2 （因为是完全二叉树所以下标对应的位置都是确定的，34属于1的子节点），左侧子节点 2i+1，右侧子节点为 2i+2

基本操作

  • 向上筛选

先把新的元素放在堆的底部，向上比较，如果比父元素的优先级高就互换位置

  • 向下筛选

当我们取出优先级最高的元素时，先把堆底部的元素放在堆顶，然后不断向下筛选

初始化

初始化一个数量为 n的 堆的时间复杂度是 O(n)

leetcode 347

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

  • 借助 哈希表 来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率
  • 维护一个元素数目为 k 的最小堆
  • 每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较
  • 如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中
  • 最终，堆中的 k 个元素即为前 k 个高频元素 ```jsx /**
    • @param {number[]} nums
    • @param {number} k
    • @return {number[]} */ var topKFrequent = function (nums, k) { var freq = new Map() // 记录每个数字出现的频率 nums.forEach((v) => { if (!freq.has(v)) { freq.set(v, 1) } else { freq.set(v, freq.get(v) + 1) } }) //构建一个只有k个元素的小顶堆结构heap var heap = [], len = 0 freq.forEach((value, key) => { if (len < k) { heap.push(key) if (len === k - 1) buildHeap(heap, freq, k) //初试化heap为堆结构 } else { if (freq.get(heap[0]) < value) {
      1. heap[0] = key //小顶堆的顶部为最小的，如果有比它更大的就更改
      2. heapify(heap, freq, k, 0) //更改堆顶元素破坏了堆结构，执行heapify再次将数组转换为堆
      } } len++ }) return heap };

// 构造堆 let buildHeap = (heap, map, k) => { for (let i = Math.floor(k-1 / 2); i >= 0; i—) { heapify(heap, map, k, i) } }

// 将数组变为堆结构 let heapify = (heap, freq, k, i) => { var left = 2 i + 1, //i的左子节点 right = 2 i + 2, //i的右子节点 min = i if (freq.get(heap[left]) < freq.get(heap[min]) && left < k) { min = left } if (freq.get(heap[right]) < freq.get(heap[min]) && right < k) { min = right } if (min !== i) { ;[heap[i], heap[min]] = [heap[min], heap[i]] heapify(heap, freq, k, min) } } topKFrequent([1,2,3,1,1,1,2,2,4,4,4,4],3) ```

  • 先用k个元素建堆
  • let i = Math.floor(k-1 / 2) 建子树
  • heap[0] = key改变堆顶之后 heapify 从 0 开始比较堆顶左右和堆顶的大小