专栏首页数据结构与算法(JavaScript)前端学数据结构与算法(七): 从零实现优先队列-堆及其应用
原创

前端学数据结构与算法(七): 从零实现优先队列-堆及其应用

前言

为什么说树结构是01世界里最重要的数据结构,因为只要调整一下节点的存储顺序或枝杈多少,解决问题的类型就可以完全不同。本章介绍的堆也是二叉树的一种,与二叉搜索树想比,只是改变了节点存放值的规则,它遵循的规则就是每个父节点的值必须大于或等于孩子节点的值,这种数据结构是二叉堆,也可以叫它优先队列。

什么是优先队列?

上一章我们介绍了普通队列,固定的从队尾入队,从队首出队。假如现在的场景需求是,出队时每次必须出队优先级最高的元素,你可能会说,这还不简单么,只需要出队时遍历整个队列,从里面找到优先级最高的元素出队,然后再队列里移除该元素即可。这样确实能满足场景的需求,但也会出现一个问题,就是出队效率太低,如果使用的是数组,找到优先级最高的元素需要O(n)的时间,然后出队该元素数组又需要O(n)的位移操作,也就是说每次出队需要消耗O(n²)的时间,这个有点太奢侈。

而堆这种数组结构就是专门用来解决这一类的问题,同样是使用数组,同样每次出队优先级最高的元素,却可以把入队和出队的操作稳定的保持在O(logn),虽然普通队列入队是O(1),但从入队出队的平均复杂度来看,性能的差距是O(log)O(n²)。我们来看下在处理十万条数据的出队/入队时,堆与普通队列之间的性能差距。

百万级别的数据时家用机已经卡死,而堆依然可以一秒之内处理完,并且随着数据规模的增加,它们之间的性能差距倍数只会越来越大。

什么是堆?

[37, 22, 26, 12, 11, 25, 7, 3, 8, 10],初看起来这是一个数组,但如果我们把它按照二叉树的结构排列起来,就会出现图下的结构:

而这就是一个堆,它有几个特点:

1. 父节点优先级高于或等于子节点

堆最显著的特点就是所有父节点的优先级都高于或等于孩子节点。这里的堆为最大堆,根节点的值最大,任意节点的排列顺序皆是如此。还有最小堆,也就是所有父节点的值小于或等于孩子节点,根节点的值最小。

2. 完全二叉树

堆的排列都是一颗完全二叉树,除去最底层的叶子节点,它就是一颗满二叉树,而且所有的叶子节点全部都朝树的左侧摆放。之前二叉树特性章节已经有所说明,只要是满二叉树使用数组是最佳存储方式。

3. 动态性

与二叉搜索树类似,当往构建好的堆内再添加或取出元素时,为了不破坏堆的性质,堆有自己的一套操作,无论何时添加/移除多少元素,始终不会破坏堆的性质。

从零实现最大堆

使用数组来表示二叉树,最大的问题是当前节点没有指向孩子节点的指针,其实这问题很好解决,通过当前节点的下标可以求出它的父节点和左右孩子节点,这也是使用数组存储的优势:

解决了这个难点后,我们首先写出最大堆的辅助函数:

class MaxHeap {
  constructor() {
    this._data = [] // 存储堆里的数据
  }
  getParent(i) { // 获取父节点
    return (i - 1) / 2 | 0 // 向下取整
  }
  getLeftChild(i) { // 获取左孩子
    return i * 2 + 1
  }
  getRightChild(i) { // 获取右孩子
    return i * 2 + 2
  }
}

增(siftUp)

往堆里添加任意元素而又不能破坏堆的性质,首先将添加的元素推入堆数组的末尾,然后这个元素需要与自己的父节点进行比较,如果比父节点大,那么它们之间就需要位置交换。交换位置之后继续与之前当前位置的父节点进行比较,如果还是比父节点大,就继续交换,直到遇到不大于父节点或已经达到根节点为止。这个操作也叫siftUp,让节点一步步的进行上浮。

class MaxHeap {
  constructor() {
    this._data = [] // 存储堆里的数据
  }
  ...
  
  push(val) {
    this._data.push(val) // 添加到队尾
    this.siftUp(this._data.length - 1) // 上浮队尾元素
  }
  siftUp(i) {
    const parent = this.getParent(i) // 获取父节点的值
    if (this._data[i] > this._data[parent]) { // 如果大于父节点的值
      this.swap(i, parent) // 交换位置
      this.siftUp(parent) // 继续上浮
    }
  }
  swap(i, j) { // 交换数组两个元素的位置
    [this._data[i], this._data[j]] = [this._data[j], this._data[i]]
  }
}

取(siftDown)

费了这么多事,都是为了出队的元素是优先级最高的,很明显,直接出队堆顶的元素即可,但出队后,根节点就为空,这个时候就破坏了堆的性质。所以堆又有对应的出队操作siftDown,堆顶出队后,将堆数组的最后一个元素放入堆顶,然后将堆顶的元素与它的左右孩子进行比较,与其中最大值的孩子交换位置,直至大于两个孩子节点或到达根节点即可。

class MaxHeap {
  constructor() {
    this._data = [] // 存储堆里的数据
  }
  ...
  
  sift() { // 出队
    if (this._data.length === 0) {
      return
    }
    const max = this._data[0] // 缓存出队元素
    this.swap(0, this._data.length - 1) // 顶尾交换
    this._data.pop() // 移除队尾
    this.siftDown(0) // 将换上来的节点进行下沉
    return max // 返回应该出队的元素
  }
  
  siftDown() {
    const { _data } = this
    let max = this.getLeftChild(i) // 假如左孩子大
    if (max >= _data.length) { // 左孩子界限超出,递归终止
      return
    }
    if (max + 1 < _data.length && _data[max + 1] > _data[max]) {
      // 如果有右孩子且右孩子比左孩子大,max+1变为右孩子的下标
      max++
    }
    if (_data[i] < _data[max]) { // 如果孩子节点大于当前节点,执行下沉操作
      this.swap(i, max) // 交换当前节点与孩子节点的位置
      this.siftDown(max) // 在孩子节点的位置继续递归
    }
  }
}

下沉操作的关键是找到两个孩子节点里面比较大的那位进行交换,交换之后在孩子节点的位置进行递归即可。以上就是堆最重要两个操作,入队和出队,已经算是从零完成了堆,不过有两个堆的辅助函数,可以更加方便快速的完成堆的相应操作。

替换(replace)

现在有一个需求是出队的同时,添加一个值到堆里,可以使用前面实现的两个方法方式,首先sift取出堆顶元素,然后push进一个元素即可,不过这样的话会执行两次O(logn)的操作,我们可以封装一个replace方法,执行一次O(logn)即可。

class MaxHeap {
  constructor() {
    this._data = [] // 存储堆里的数据
  }
  ...
  
  replace(val) {
    if (this._data.length === 0) {
      return
    }
    const max = this._data[0] // 缓存出队元素
    this._data[0] = val // 将添加的元素赋值给堆顶
    this.siftDown(0) // 堆顶执行下沉操作
    return max // 出队
  }
}

数组快速堆化(heapify)

如何将一个数组快速转换为堆?直接把数组的每一项遍历添加到堆里即可,这样确实可以实现,但这个过程并不是最快的。这里我们可以借助完全二叉树的特性,以最后一个叶子节点的父节点为起点,把起点节点到根节点之间的所有节点进行下沉操作即可。这样的话,平均可以省去一半节点的操作,通过我看不懂的证明得知可从O(nlogn)变为O(n)的复杂度。

class MaxHeap {
  constructor(arr = []) { // 构造函数支持传入数组,快速堆化
    if (Array.isArray(arr) && arr.length > 0) {
      this._data = [...arr]
      this.heapify(this._data)
    } else {
      this._data = [] // 存储堆里的数据
    }
  }
  ...
  
  heapify(arr) {
    let parent = this.getParent(arr.length - 1)
    while (parent >= 0) {
      this.siftDown(parent)
      parent--
    }
  }
}

堆的应用

以上代码我们从零实现了一个堆,但它有什么用了?接下来介绍几个示例来说明这种数据结构的作用,及在处理特定问题时的巧妙。

堆排序 ↓

从上面实现的最大堆不难发现,既然每次堆顶都是最大的值,那我们依次出队整个堆,那不实现了一次降序的排序么?依照这个特性,构建一个最小堆来实现一个排序算法试试!

function heapSort(arr) {
  let last = ((arr.length - 2) / 2) | 0; // 只需要从最后一个叶子的父节点开始
  const ret = [];
  while (last >= 0) {
    siftDown(arr, last, arr.length); // 下沉一半的节点实现堆化
    last--;
  }
  while (arr.length > 0) {
    ret.push(arr[0]); // 将堆顶元素放入新数组内
    [arr[0], arr[arr.length - 1]] = [arr[arr.length - 1], arr[0]]; // 交换首尾的元素
    arr.pop(); // 将交换的堆顶元素去掉
    siftDown(arr, 0, arr.length); // 重新下沉堆顶,不破坏堆的性质
  }
  return ret; // 返回排序好的数组
  
  function siftDown(arr, i, n) {
    let left = i * 2 + 1;
    if (left >= n) {
      return;
    }
    if (left + 1 < n && arr[left] > arr[left + 1]) { // 改为判断谁小谁 +1
      left++;
    }
    if (arr[left] < arr[i]) { // 让大元素下沉
      [arr[left], arr[i]] = [arr[i], arr[left]];
      siftDown(arr, left, n);
    }
  }
}

虽然我们完成了排序的任务,但这个算法我们另外开辟了O(n)的空间去存放新的排序好的数组,那有没可能省掉这个额外的空间了,答案是有的,可以使用原地堆排序的方式,我们来实现它!

原地堆排序 ↓

也就是在原数组上直接进行排序,而不借助额外空间,它的实现原理是使用最大堆,构建好了之后将堆顶元素与末尾进行交换,而后缩小右边界,重新构建堆,依次执行上述过程即可。

function heapSort(arr) {
  let last = ((arr.length - 1) / 2) | 0;
  while (last >= 0) {
    siftDown(arr, last, arr.length); // 使用最大堆
    last--;
  }
  let r = arr.length;
  while (r > 0) {
    [arr[0], arr[r - 1]] = [arr[r - 1], arr[0]]; // 将堆顶与末尾元素交换
    r--; // 右边界减1
    siftDown(arr, 0, r); // 重新下沉堆顶元素
  }
  
  function siftDown (arr, i, n) {
    let left = i * 2 + 1;
    if (left >= n) {
      return;
    }
    if (left + 1 < n && arr[left] < arr[left + 1]) { // 大顶堆
      left++;
    }
    if (arr[i] < arr[left]) { // 下沉小元素
      [arr[i], arr[left]] = [arr[left], arr[i]];
      siftDown(arr, left, n);
    }
  };
}

1046-最后一块石头的重量 ↓

有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。
假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
如果 x === y,那么两块石头都会被完全粉碎;
如果 x !== y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0。

输入:[2,7,4,1,8,1]
输出:1
解释:
先选出 7 和 8,得到 1,所以数组转换为 [2,4,1,1,1],
再选出 2 和 4,得到 2,所以数组转换为 [2,1,1,1],
接着是 2 和 1,得到 1,所以数组转换为 [1,1,1],
最后选出 1 和 1,得到 0,最终数组转换为 [1],这就是最后剩下那块石头的重量。

这题取巧的地方就在于每次要找到最大的两块石头,那我们使用最大堆来解这题就非常适合了,取两次堆顶的元素元素即可,而后把相减的绝对值放入堆顶,重新下沉一次维持堆的性质即可,当堆里的元素只剩一个时结束这个过程。代码如下:

 const lastStoneWeight = function (stones) {
  let last = ((stones.length - 2) / 2) | 0;

  while (last >= 0) { // 堆化
    siftDown(stones, last);
    last--;
  }

  while (stones.length > 1) { // 当只有一个元素结束循环
    swap(stones, 0, stones.length - 1) // 首尾交换
    const first = stones.pop() // 取出尾巴里的最大值
    siftDown(stones, 0) // 执行下沉维持堆
    const second = stones[0] // 再取出堆顶的元素,即为第二大的元素
    const diff = Math.abs(first - second) // 求出绝对值
    stones[0] = diff // 将绝对值覆盖堆顶
    siftDown(stones, 0) // 再次维持堆
  }
  return stones[0];

  function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]]
  }

  function siftDown(arr, i) {
    let left = i * 2 + 1;
    if (left >= arr.length) {
      return;
    }
    if (left + 1 < arr.length && arr[left] < arr[left + 1]) {
      left++;
    }
    if (arr[left] > arr[i]) {
      swap(arr, left, i)
      siftDown(arr, left);
    }
  }
};

堆是用的数组实现,所以尽可能的不让数组有位移的操作,这个非常有必要考虑。

215-数组中的第K个最大元素 ↓

最简单的解法就是先使用sort函数排序,然后选取对应下标的元素即可,但如果面试官出了这个题目,那么想看到肯定就不是这么一个O(nlogn)的暴力解法了,借助本章学习的堆,我们可以交出O(nlogk)的解法。如果是求100万数据的第100大小的数字,这个优化还是很有益的。

首先说明思路,构建一个k大小的最小堆,之后遇到的元素如果大于堆顶,就替换堆顶的元素,执行下沉操作,保持堆的性质,最后当整个数组遍历完,这个最小堆的堆顶就是需要返回的元素了,因为比第k大的全部在堆顶的下面。

var findKthLargest = function (nums, k) {
  const minHeap = [] // 最小堆
  for (let i = 0; i < nums.length; i++) {
    if (i < k) { // 堆的大小还没达到k
      minHeap.push(nums[i]) // 直接push
      siftUp(minHeap, minHeap.length - 1) // 执行上浮操作维持堆的性质
    } else if (nums[i] > minHeap[0]) { // 如果下一个元素大于堆顶
      minHeap[0] = nums[i] // 替换堆顶元素
      siftDown(minHeap, 0) // 执行下沉操作维持堆性质
    }
  }
  return minHeap[0] // 最后返回最小堆堆顶元素即可
};

function siftUp(nums, i) {
  const parent = (i - 1) / 2 | 0
  if (nums[i] < nums[parent]) { // 将小的元素上浮
    swap(nums, i, parent)
    siftUp(nums, parent)
  }
}

function siftDown(nums, i) {
  let l = i * 2 + 1
  if (l + 1 > nums.length) {
    return
  }
  if (l + 1 <= nums.length && nums[l] > nums[l + 1]) {
    l++  // 选取小的元素
  }
  if (nums[i] > nums[l]) { // 将大的元素下沉
    swap(nums, i, l)
    siftDown(nums, l)
  }
}

function swap(nums, i, parent) {
  [nums[i], nums[parent]] = [nums[parent], nums[i]]
}

373-查找和最小的K对数字 ↓

给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。
定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2。
找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数:
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

依次遍历嵌套的两个数组,这个是无可避免的,但这题我们能优化的是这个计算结果的存放,不使用暴力的每次计算后进行排序。使用堆即可,维持一个k大小的最大堆,每次计算的值与堆顶元素进行比较,如果比堆顶的小,就放入堆里,最后重新排序这个k大小的堆即可。

var kSmallestPairs = function (nums1, nums2, k) {
  const heap = []
  for (let i = 0; i < nums1.length; i++) {
    for (let j = 0; j < nums2.length; j++) {
      if (heap.length === k && nums1[i] + nums2[j] >= (heap[0][0] + heap[0][1])) {
        // 因为都是升序的数组,所以当这次的和大于堆顶时,
        // 那么之后的循环也一定是大于的,所以跳出这轮循环即可。
        break
      }
      if (heap.length < k) { // 堆没有满时
        heap.push([nums1[i], nums2[j]])
        siftUp(heap, heap.length - 1) // 构建最大堆
      } else if ((nums1[i] + nums2[j]) <= sum(heap[0])) { // 只有当小于堆顶时
        heap[0] = [nums1[i], nums2[j]] // 替换堆顶的元素
        siftDown(heap, 0) // 维持最大堆
      }
    }
  }
  return heap.sort((a, b) => (a[0] + a[1]) - (b[0] + b[1]))
  // 因为是最大堆,所有返回升序的顺序
};

function siftUp(heap, i) {
  const parent = (i - 1) / 2 | 0
  if (sum(heap[i]) > sum(heap[parent])) {
    swap(heap, i, parent)
    siftUp(heap, parent)
  }
}

function siftDown(heap, i) {
  let left = i * 2 + 1
  if (left >= heap.length) {
    return
  }
  if (left + 1 < heap.length && sum(heap[left]) < sum(heap[left + 1])) {
    left++
  }
  if (sum(heap[i]) <= sum(heap[left])) {
    swap(heap, i, left)
    siftDown(heap, left)
  }
}

function sum(arr) { // 求和
  return arr[0] + arr[1]
}

function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]]
}

最后

写了这么多,不难发现无非就是siftupsiftdown函数的编写, 只要熟练掌握堆的这两种操作,基本上来说堆也就掌握了90%。还有最主要的是熟悉堆的思想,针对前k类似的题目,使用堆都是非常适合的,而堆的动态性又非常适合处理数据随时有新元素加入的场景。居然有这么cool的数据结构~ 本章github源码

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 前端学数据结构与算法(十):深入理解快速排序

    上一章我们已经实现了快速排序,在数据理想化的情况下,上一章的快排性能确实也不错,但如果数据比较极端的,快排的O(nlogn)就不太稳定了,本章将介绍几种快排应对...

    飞跃疯人院
  • 前端学数据结构与算法(九):常见五种排序算法的实现及其优缺点

    数据结构章节暂时告一段落,从这一章节开始算法之旅。首先从排序开始,排序作为最基础的算法,一点也不简单,写一个快排、堆排、归并排序在大厂面试中并不罕见,或者某些题...

    飞跃疯人院
  • 前端学数据结构与算法(十一):看似简单又让人抓狂的二分查找算法

    二分查找法是一种高效的查找算法,它的思想非常好理解,但编写正确的二分查找并不简单。本章从最基础的二分查找实现开始,讲解其编写技巧,接下来介绍它的四个常见变种的编...

    飞跃疯人院
  • 前端排序算法实现

    前端迷
  • 算法面试经常需要你手写的三个排序算法(Python语言)

    五分钟学算法
  • LeetCode111|独一无二的出现次数

    键值对HashMap的重要性真的是不言而喻的,因为它应用的太广泛了,可以说基本上你做应用就是使用它,和ArrayList的次数相差不大,所以你现在如果不懂的话,...

    后端Coder
  • golang数据结构之快速排序

    具体过程:黑色标记代表左指针,红色标记代表右指针,蓝色标记代表中间值。(依次从左往向下)

    绝命生
  • Sort Algorithm排序算法

    第一次迭代,寻找0到6个下标的数字哪个是最小的,找到最小的就和第一个交换,也就是2。第一次遍历所有

    西红柿炒鸡蛋
  • LeetCode 1426. 数元素(哈希set)

    给你一个整数数组 arr, 对于元素 x ,只有当 x + 1 也在数组 arr 里时,才能记为 1 个数。

    Michael阿明
  • LeetCode 912. 排序数组(10种排序)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sort-an-array 著作权归领扣网络所有。商...

    Michael阿明

扫码关注云+社区

领取腾讯云代金券