写文章

JS图文讲解堆以及实现

吐槽君 分类：javascript

堆的定义

堆（heap），是一种数据结构

根据 维基百科 的定义，堆 是一种特别的二叉树，满足以下条件的二叉树，可以称之为 堆：

  • 完全二叉树；
  • 每一个节点的值都必须 大于等于或者小于等于 其孩子节点的值。

堆的优势：

  • 插入和删除都是O(lg n)
  • 取最大/最小值得时间为O(1)

根据父子节点值的关系，堆可以分为：

  • 最大堆(max-heap)，子节点的值小于等于父节点
  • 最小堆(min-heap)，子节点的值大于等于父节点

最大堆的实现

在JS里，没有内置的堆，也没有优先队列，所以得自己手动实现。
一般堆是由数组来实现的，堆是一颗完全二叉树，其每个节点从上到下，从左到右排好序后。

这里有几个点要重点说明一下：

  1. 堆的起始序号是1而不是0
  2. 节点x的左子节点为2x，右子节点为2x+1，父节点为x/2 (向下取整)
  3. 堆的大小为n, 则[n/2 + 1...n]都是叶子节点
  4. 我们在用堆的序号访问数组时需要-1
  5. 堆的大小和数组的长度没有划等号的联系

maxHeapify

对于树的算法，一般递归是简单且直观的。
我们先定义一个操作，它可以将一个子树最大堆化。

// h 为堆数组
// i 为子树的根节点下标
// size 为堆的大小
function maxHeapify(h, i, size) {}

我们假设该子树的左右节点都是最大堆。
首先我们判断根节点，左右子节点的值大小，如果子节点的值大于根节点，则互换。
最后对被换掉的节点进行再最大堆化(递归)。

截屏20210419 下午3.40.10.png

tip: 注意数组的长度可能比实际的堆大，所以我们需要一个size表示堆的大小。

buildMaxHeap

有了对子树进行堆化的操作，我们就可以循环递归将整个数组堆化。
由于我们的假设是子树都是最大堆，那么我们应该是从子节点开始往上堆化。也就是说我们得从数组的尾部往前进行迭代。因为堆的尾部都是子节点，而子节点满足最大堆的特性。

function buildMaxHeap(nums) {
  for (let i = nums.length; i > 0; i--) {
    maxHeapify(nums, i, nums.length);
  }

  return nums;
}

截屏20210419 下午3.52.21.png

最小堆

实现完最大堆后其实最小堆也就是判断条件变了而已。

算法题：堆排序

原理：堆的堆顶元素一定是最大/小值，我们每次将堆顶元素和堆尾元素互换，然后将堆的大小减一，再对堆顶堆化。然后我们再对新的堆重复操作，直到堆大小为1。

每次堆化的时间为O(lgn)，建堆的时间为O(n)，我们一共会执行n次堆化，所以堆排序的时间复杂度为O(nlgn)。

截屏20210419 下午3.15.34.png

优先队列

优先队列(priority queue)是堆的一种应用。

优先队列具有最高级先出 （first in, largest out）的行为特征

优先队列的一个应用是计算机系统的作业调度。每次都将执行优先级最高的作业。

最大优先队列支持以下几个操作：

  1. insert 插入一个节点
  2. maximum 取最大节点
  3. extractMax 提取最大节点

insert

插入操作的步骤为：

  1. 将新节点放到堆尾，然后找寻其父节点，如果父节点的值小于新节点，则交换节点。
  2. 重复步骤一直到父节点的值大于新节点或者没有父节点。

截屏20210419 下午2.54.59.png

另外，我们还可以用插入法建堆。

maximum

取堆数组的第一个元素

extractMax

其实在堆排序的时候有用到这个概念，就是将堆顶元素和堆尾元素互换，然后将堆大小-1，重新堆化堆顶。

截屏20210419 下午3.24.14.png

算法题：第K大元素

给一堆数据，求出其中第K大的元素。
比如[1,2,3,3,4]其中第3大的元素是3，也就是重复的也计数。

这题我们可以用堆来解决，当然也可用暴力法，先排序，然后返回第K个元素，最快的时间复杂度为O(nlgn)。

我们知道数组的插入和删除是O(n)的，但是堆的插入删除只有O(lgn)。
如果我们维护一个大小为K的堆，那么这个堆就可以存储前K大的数或者前K小的数，然后我们再取堆顶，也就是第K大/小的树。因为插入删除的时间复杂度为O(lgk)，我们最多执行n次插入删除。用堆的时间复杂度就为O(nlgk)，空间复杂度为O(k)。

var findKthLargest = function (nums, k) {
  var heap = [];
  for (let i = 0; i < nums.length; i++) {
    const el = nums[i];

    if (heap.length === k && el > heap[0]) {
      heap[0] = el;
      minHeapify(heap, 1, k);
    }

    if (heap.length < k) {
      minHeapInsert(heap, el);
    }
  }

  return heap[0];
};

当然还有线性时间级的解法，主要通过分治思想，我们随机选取参照将数组划分为左右两边（左边比参照小），然后判断K的位置，再递归左或者右子数组。其算法时间复杂度为O(n)，最坏情况下为O(n^2)，但是划分是随机的，所以一般不会存在最坏情况。

文章源码

历史精选

  1. 如何在10分钟之内完成一个业务页面 - Vue的封装艺术
  2. 新手也能看懂的虚拟滚动实现方法
  3. Vue3有哪些不向下兼容的改变
  4. 精细控制transition细节 - 实现一个活泼的弹框

原文-我的小破站

回复

我来回复

  • 暂无回复内容