关于leetcode个人解题总结:大厂算法面试之leetcode精讲12堆

47次阅读

共计 2314 个字符,预计需要花费 6 分钟才能阅读完成。

大厂算法面试之 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;}
}

正文完
 0