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

视频教程(高效学习):点击学习

延伸:

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

完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层从右向左连续缺若干结点,这就是完全二叉树。

ds_208

堆是一个完全二叉树,所以我们可以采用数组实现,不会浪费太多空间,堆中的每个节点的值总是不大于或不小于其父节点的值,堆分为大顶堆和小顶堆,大顶堆堆顶是元素中最大的一个,小顶堆堆顶是最小的,在向堆中加入元素的时候,能动态调整堆内元素的顺序,始终保持堆的性质。

堆的特点:
  • 内部数据是有序的
  • 可以弹出堆顶的元素,大顶堆就是弹出最大值,小顶堆就是弹出最小值
  • 每次加入新元素或者弹出堆顶元素后,调整堆使之重新有序仅需要O(logn)的时间
堆的实现
  • 用数组实现,堆从上到下,从左到右一一对应数组中的元素
  • 节点父节点索引 parentIndex = [(index - 1) / 2],左节点索引leftIndex = index * 2 + 1,右节点索引 rightIndex = index * 2 + 2
  • 第一个非叶子节点是[size / 2]
向堆中添加元素
  • 把新数据添加到树的最后一个元素,也就是数组的末尾
  • 把末尾节点向上调整,即bubbleUp
  • 时间复杂度O(logn)

动画过大,点击查看

弹出堆中的元素
  • 交换根节点与最后一个节点的值
  • 删除最后一个节点
  • 把根节点向下调整
  • 时间复杂度O(logn)

动画过大,点击查看

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

ds_115

完整代码
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;
    }
}
最新:
react源码解析
搞定大厂算法面试之leetcode精讲
vue3.0源码解析(筹划中)

潇晨简介:前阿里、道富前端工程师,撸过码、创过业,热于技术分享,很高兴认识你
愿景:做一个程序员高效深度学习社区
请尊重劳动果实 否则追究法律责任

公众号
管理员wx