堆的基础知识和相关算法

堆的基础知识和相关算法

堆的定义

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

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),但是划分是随机的,所以一般不会存在最坏情况。

文章源码

上一篇 二叉搜索树基本知识及相关算法
下一篇 超实用教程 - SVG Icon封装