大厂算法面试之leetcode精讲12.堆

视频解说（高效学习）:点击学习

目录：

1.开篇介绍

2.工夫空间复杂度

3.动静布局

4.贪婪

5.二分查找

6.深度优先&广度优先

7.双指针

8.滑动窗口

9.位运算

10.递归&分治

11剪枝&回溯

12.堆

13.枯燥栈

14.排序算法

15.链表

16.set&map

17.栈

18.队列

19.数组

20.字符串

21.树

22.字典树

23.并查集

24.其余类型题

延长：

满二叉树：除叶子节点外，所有的节点都有两个子节点，这类二叉树称作满二叉树（Full Binarry Tree)，如下图：

齐全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左间断缺若干结点，这就是齐全二叉树。

堆是一个齐全二叉树，所以咱们能够采纳数组实现，不会节约太多空间，堆中的每个节点的值总是不大于或不小于其父节点的值，堆分为大顶堆和小顶堆，大顶堆堆顶是元素中最大的一个，小顶堆堆顶是最小的，在向堆中退出元素的时候，能动静调整堆内元素的程序，始终保持堆的性质。

堆的特点：
  • 外部数据是有序的
  • 能够弹出堆顶的元素，大顶堆就是弹出最大值，小顶堆就是弹出最小值
  • 每次退出新元素或者弹出堆顶元素后，调整堆使之从新有序仅须要O(logn)的工夫
堆的实现
  • 用数组实现，堆从上到下，从左到右一一对应数组中的元素
  • 节点父节点索引 parentIndex = [(index - 1) / 2]，左节点索引leftIndex = index * 2 + 1，右节点索引 rightIndex = index * 2 + 2
  • 第一个非叶子节点是[size / 2]
向堆中增加元素
  • 把新数据增加到树的最初一个元素，也就是数组的开端
  • 把开端节点向上调整，即bubbleUp
  • 工夫复杂度O(logn)

动画过大，点击查看

弹出堆中的元素
  • 替换根节点与最初一个节点的值
  • 删除最初一个节点
  • 把根节点向下调整
  • 工夫复杂度O(logn)

动画过大，点击查看

从一个数组中取出最小值的复杂度：

残缺代码
class Heap {    constructor(comparator = (a, b) => a - b, data = []) {        this.data = data;        this.comparator = comparator;//比拟器        this.heapify();//堆化    }    heapify() {        if (this.size() < 2) return;        for (let i = Math.floor(this.size()/2)-1; i >= 0; i--) {            this.bubbleDown(i);//bubbleDown操作        }    }    peek() {        if (this.size() === 0) return null;        return this.data[0];//查看堆顶    }    offer(value) {        this.data.push(value);//退出数组        this.bubbleUp(this.size() - 1);//调整退出的元素在小顶堆中的地位    }    poll() {        if (this.size() === 0) {            return null;        }        const result = this.data[0];        const last = this.data.pop();        if (this.size() !== 0) {            this.data[0] = last;//替换第一个元素和最初一个元素            this.bubbleDown(0);//bubbleDown操作        }        return result;    }    bubbleUp(index) {        while (index > 0) {            const parentIndex = (index - 1) >> 1;//父节点的地位            //如果以后元素比父节点的元素小，就替换以后节点和父节点的地位            if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {                this.swap(index, parentIndex);//替换本人和父节点的地位                index = parentIndex;//一直向上取父节点进行比拟            } else {                break;//如果以后元素比父节点的元素大，不须要解决            }        }    }    bubbleDown(index) {        const lastIndex = this.size() - 1;//最初一个节点的地位        while (true) {            const leftIndex = index * 2 + 1;//左节点的地位            const rightIndex = index * 2 + 2;//右节点的地位            let findIndex = index;//bubbleDown节点的地位            //找出左右节点中value小的节点            if (                leftIndex <= lastIndex &&                this.comparator(this.data[leftIndex], this.data[findIndex]) < 0            ) {                findIndex = leftIndex;            }            if (                rightIndex <= lastIndex &&                this.comparator(this.data[rightIndex], this.data[findIndex]) < 0            ) {                findIndex = rightIndex;            }            if (index !== findIndex) {                this.swap(index, findIndex);//替换以后元素和左右节点中value小的                index = findIndex;            } else {                break;            }        }    }    swap(index1, index2) {//替换堆中两个元素的地位        [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];    }    size() {        return this.data.length;    }}