复杂度分析

事后统计法的局限性：

1. 测试结果非常依赖测试环境。

2. 测试结果受数据规模的影响很大。



时间复杂度公式 T(n) = O(f(n))

T(n)表示代码执行的时间；n表示数据规模的大小

f(n)表示每行代码执行的次数总和

大O时间复杂度并不表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫做渐进时间复杂度，简称时间复杂度。



分析时间复杂度的方法

1. 只关注循环次数最多的一段代码。

2. 总复杂度等于量级最大的那段代码的复杂度。

3. 嵌套代码的复杂度嵌套外代码复杂度的乘积。



时间复杂度案例分析：

1. 常量阶O(1) 数量确定的几行代码

2. 指数阶O(2^n)

3. 对数阶O(logn) 循环中变量i的值从1开始取，没循环一次就乘以2

4. 线性阶O(n)

5. 线性对数阶O(nlogn) 归并排序，线性排序

6. 平方阶O(n^2)

7. 立方阶O(n^3)

8. K次方阶O(n^k)

9. 阶乘阶O(n^2)

空间复杂度分析 表示算法的存储空间与数据规模之间的增长关系

常用的空间复杂度O(1),O(n),O(n^2)



1. 最好时间复杂度

2. 最坏时间复杂度

3. 平均情况时间复杂度

4. 均摊时间复杂度 对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间 存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一起分析，看是否能将较高时间复杂度的那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上，而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

分析add（）函数的时间复杂度：

看了两个别人的答案：最好是O(1)，最差是O(n), 均摊是O(1)

我自己得出的结论是均摊O（1），仅仅从整体进行计算，没有

考虑到add只是一次操作行为，需要计算的是每次执行的复杂度

通过这个练习，较为深刻的理解到一段代码的执行时间，在不同

情况下是不一样的。



数组



数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组相同类型的数据。



线性表：





数组的特点：

1.线性表

2.连续的内存空间和相同类型的数据



数组的删除，最好时间复杂度是O(1),最坏时间复杂度是O(n),

平均时间复杂度是O(n) 在某种场合下并不一定非得追求内存的连续性，

如果将多次删除操作集中执行，会提高效率。JVM标记清除的算法思想就是这样。



容器类ArrayList：

优势：

1.可以将数组操作的细节封装起来。

2.支持动态扩容

注意：扩容操作涉及内存申请和数据搬迁，比较耗时，所以如果事先能确定需要存储的数据大小，最好在创建ArrayList的时候先指定数据的大小。

如果做一些底层的开发，如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。



链表

常见的缓存淘汰策略：

1.先进先出策略 FIFO

2.最少使用策略LFU

3.最近最少使用策略LRU

链表常见的类型：

1.单链表

2.双链表

3.循环链表

内存块成为链表的结点

每个链表的结点除了要储存数据之外，还需要记录链上的下一个结点的地址。

两个特殊的结点：

1.头结点 用来记录链表的基地址

2.尾结点 不是指向下个节点，而是指向一个空地址NULL

循环链表是一个特殊的单链表，和单链表唯一的区别就在尾结点

其指向头结点。优点是从链尾到链头比较方便。要处理的数据具有环形结构特点时，就特别适合采用循环链表。

双向链表

比单链表占用更多的内存空间，支持双向遍历，带来了双向链表操作的灵活性。双向链表在某些情况下的插入删除等操作都要比单链表简单，高效。

在已知要删除的节点的时候，双向链表中已经保存了前驱节点的指针，不需要想单链表那样遍历。单链表删除操作需要O(n)的时间复杂度，而双向链表只需要在O(1)的时间复杂度内就搞定了。

查询数据也会有优势，可以记录上次查找的位置P，每次查询时，根据要查找的值与P的大小关系，决定是往前还是往后查找，平均只需要一半的数据。

双向链表使用的是空间换时间的思想

当内存空间充足的时候，如果更加追求代码的执行速度，就可以选择空间复杂度相对较高，但时间复杂度相对很低的算法或者数据时间。相反，如果内存比较紧缺，就要反过来用时间换空间的思路。

缓存就是利用了空间换时间的设计思想





基于链表实现LRU缓存淘汰算法

思路：维护一个有序单链表，越靠近尾部的节点是越早之前访问的，当有一个新的数据被访问时，我们从链表头开始顺序遍历链表

1.如果此数据之前已经被缓存在链表中了，我们遍历得到这个数对应的结点，并将其从原来的位置删除，然后在插入到链表的头部。

2.如果此数据没有存在缓存链表中，又可以分为两种情况：

• 如果此时存储未满，则将此节点直接插入到链表的头部

• 如果此时缓存已满，则链表尾结点删除，将新的数据节点插入链表的头部。



栈



栈是一种操作受限的线性表

当某个数据集合只涉及在一端插入和删除数据，并且满足后进行先出、先进后出的特性，我们就应该首选栈这种数据结构

栈既可用数组来实现，也可以用链表来实现。用数组实现的栈，叫做顺序栈，用链表实现的栈叫做链式栈。

典型的应用场景：

1.函数调用栈 操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种数据结构，用来存储函数调用时的临时变量，每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

2.表达式求值 编译器通过两个栈来实现，一个保存操作数的栈，另一个保存运算符的栈。从左向右遍历表达式，当遇到数字，加压入操作数栈，当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符入栈，如果比运算符栈顶元素的优先级低级或者相同，从运算符栈顶取栈顶运算符，从操作数栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

3.在括号匹配中的应用：

用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中，当扫描到右括号时，从栈顶取出一个左括号。如果能匹配，则继续扫描剩下的字符串，如果遇到不能配对的右括号，或者栈中没有数据，说明为非法格式。当所有的括号扫描完成之后，如果栈为空，则说明字符串为合法格式。 {[] ()[{}]}或[{()}([])] 根据这个格式，按照这个思路确实是一个非常好的方法

如何用栈实现浏览器的前进后退功能：

使用两个栈，G和Z，把首次浏览的页面依次压入栈G，当点击后退按钮时，在依次从G中出栈，并将出栈的数据依次放入栈Z。当点击前进按钮时，依次从Z栈中取出数据，放入栈G中。当栈G中没有数据时，那就说明没有页面可以继续浏览， 当Z中没有数据时，那就说明没有页面可以点击前进按钮浏览了。



队列

CPU的资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反过多的线程反而会导致CPU频繁的切换，处理性能下降。所以线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。

队列也是一种操作受限的线性表数据结构

java语言的高级用法



基于链表的队列的实现方法

循环队列，避免数据搬迁

队列这种数据结构很基础，平时的业务开发不大可能从零实现一个队列，甚至都不会直接用到。而一些具有特殊特性的队列应用却比较广泛，比如阻塞队列和并发队列

阻塞队列就是在队列的基础上增加了阻塞操作 队列为空的是，从队列头取数据会被阻塞，直到队列中有了数据才能返回。如果队列已经满了，那么插入数据的操作就会被阻塞。知道队列中有空闲的位置后再插入数据，然后再返回。

递归

递归需要满足的条件：

1.一个问题的解可以分解为几个子问题的解

2.这个问题与分解后的子问题，除了数据规模的不同，求解思路完全一样

3.存在递归终止条件

写递归代码的关键是写错递推公式，找到终止条件。

递归代码要警惕堆栈溢出 如果递归求解的数据规模很大，调通层次很深，一直压入栈，就会有堆栈溢出的风险。

递归代码要警惕重复计算 为了避免重复计算，可以通过一个数据结构来保存已经求解过的f(k)



排序

常用的排序

1. 冒泡排序

2. 插入排序

3. 选择排序

4. 归并排序

5. 快速排序

6. 计数排序

7. 基数排序

8. 桶排序



如何分析和评价一个排序算法：

1.排序算法的执行效率

• 最好情况、最坏情况、平均情况时间复杂度

• 时间复杂度的系数、常数、低阶

• 比较次数和交换次数

以上都需要背下来啊，复习

排序算法的内存消耗

算法的内存消耗可以通过时间复杂度来衡量

排序算法的稳定性

如果待排序的序列中存在相等的元素，经过排列后，相等元素之间原有的先后顺序不变



冒泡排序

最好情况下。要排序的数据已经是有序的了，只需要进行一次冒泡操作。最好情况时间复杂度是O（n）而最坏情况是，要排序的数据刚好是倒序排列的，我们需要进行n次冒泡排序，所以最坏情况时间复杂度为O(n^2)



选择排序不是一种稳定的排序算法，每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。



冒泡排序不管怎么优化，元素交换次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度

从代码实现上看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个。

归并排序和快速排序时间复杂度为O(nlogn)，适合大规模的数据排序

归并排序使用的是分治思想。

归并排序使用的就是分治思想

分治算法一般都是用递归来实现的

归并排序不是原地排序算法

空间复杂度复杂度为O（n）在任意时刻，CPU只会在一个函数执行，也就只会有一个临时的内存空间在使用，最大不会超过n.



快速排序：

归并处理的过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。



线性排序

桶排序 记数排序 基数排序 这三个算法都是基于比较的排序算法，都不涉及元素之前的比较操作

对排序的数据要求很苛刻



桶排序

将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序一次取出，组成的序列就是有序的了

桶排序对数据的要求：

1.要排序的数据需要很容易就能划分成m个桶，并且，桶与桶之间有着天然的大小顺序。

2.数据在各个桶之间的分布是比较均匀的。

桶排序适合用在外部排序中 数据储存在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中



记数排序 是桶排序的一直特殊情况

当要排序的数据范围并不大的时候

虽然没怎么看懂，但是确实很巧妙

基数排序 10万个手机号码排序



排序优化 实现一个高性能的 通用的排序函数

如何选择排序算法：如果对小规模数据进行排序，可以选择复杂度是O(n^2)的算法，如果对大规模数据进行排序，时间复杂度是O(nlogn)的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是O(nlogn)的排序算法来实现排序函数。

java语言采用堆排序实现排序函数



快速排序出现O(n^2)复杂度达到主要原因是因为分区点选的不够合理。最理想的分区点是：被分区点分开的两个分区中，数据的数据量差不多

1.三数取中法 从区间的首位中间分别取一个数，然后对比大小，取这3个数的中间值作为分区点。

2.随机法



解决快速排序递归过深导致堆栈溢出的问题：

1.限制递归深度

2.在堆适当模拟实现一个函数调用栈。

二分查找

二分查找针对的是有序的数据集合

二分查找可以用循环和递归实现

二分查找的局限性：

1.二分查找依赖的是顺序表结构

2.二分查找针对的是有序数据 没有频繁的插入，删除，可以进行一次排序多次二分查找。

3.数据量太小不适合二分查找

4.数据量太大也不适合二分查找



二分查找底层依赖的是数组，除了数据本身之外，不需要额外储存其他信息，是最省内存空间的存储方式。



二分查找的变形：

变体一：查找第一个值等于给定值的元素

尽管a[7]也等于8，但它并不是我们想要找的第一个等于8的元素

if (a[mid] > value) {

对于a[mid] > value的情况，需要更新high=mid-1

} else if (a[mid] < value) {

对于a[mid]>value的情况，需要更新low=mid+1

if ((mid == 0) || (a[mid - 1] != value)) return mid;

如果mid等于0，那这个元素已经是

变体二 ：查找最后一个值等于给定值的元素

变体三：查找第一个大于等于给定值的元素

变体四：查找最后一个小于等于给定值的元素



当要查找某个IP归属地时，可以先通过二分查找，找到最后一个起始IP小于等于这个IP的IP区间，然后，检查这个IP是否在这个IP区间内，如果在就取出对应的归属地显示，如果不在就返回未查到

对以上这个解决方案不明白，为什么要找第一个小于等于的区间呢，

和上一节课的二分查找有什么区别呢，既然你已经排序了，为什么不能用上节课那样的二分查找法



跳表 skip list 数组改造之后的数据结构

为什么redis一定要用跳表实现有序集合？

1.跳表可以做到O(logn)的时间复杂度定位区间的起点

2.跳表更容易实现代码

3.跳表更加灵活，可以通过改变所以构建策略，有效平衡执行效率和内存消耗。

跳表可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树



redis中的有序集合（Sorted Set）就是用跳表实现的

调表的思路，建立二级三级四级索引。

在调表中查询任意数据的时间复杂度是O(logn)

这种查询效率的提升前提是建立了很多级的索引，也就是空间换时间的思路



删除的时候，如果删除的这个节点在索引中也有出现，除了要删除原始链表中的结点，还要删除索引中的，因为单链表中的删除操作需要拿到要删除节点的前驱节点。



当不停地往调表中插入数据时，如果不更新索引，就可能出现某两个索引节点之间数据非常多的情况，极端情况下，跳表还会退化成单链表



跳表是通过随机函数来维护平衡性的



散列表

散列表是数组的一种扩展，由数组演化而来



解决散列冲突的方法：

1.开放寻址法

• 线性探测

• 二次探测

• 双重散列

2.链表法（对这个熟悉）



Word文档中的单词拼写功能检查功能是如何实现的？

用散列表来存储整个英文单词词典，当用户输入某个英文单词时，拿用户输入的单词去散列表中查找。如果查到，则说明拼写正确；如果没有查到则说明拼写可能错误， 给予提示。



如何打造一个工业级水平的散列表

散列表的查询效率不能笼统地说成是O(1)。它和散列函数，装载因子、散列冲突等都有关系。如果散列函数设计得不好，或者装载因子过高。都可能导致散列冲突发生的概率升高。查询效率下降。



如何设计一个可以应对各种异常情况的工业级散列表，来避免在散列冲突的情况下，散列性的急剧下降，并且能抵抗散列碰撞攻击。



散列函数设计的好坏，决定了散列表冲突的概率大小，也直接决定了散列表的性能。

好的散列函数：

1.散列函数的设计不能太复杂

2.散列函数生成的值要尽可能随机并且均匀分布。

3.综合考虑各种因素：长度，特点，分布，散列表的大小



进行扩容时，装载因子阈值需要选择得当。如果太大，会导致冲突过多；如果太小，会导致内存浪费严重。

如何避免低效地扩容：

为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在操作的过程中，分批完成。当装载因子触达阈值后，只申请新空间，但并不讲老的数据搬移到新散列表中。当有新数据要插入时，将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬迁到新散列表中了。这样，没有了集中的一次性数据搬迁，插入操作就变得很快了。



如何选择冲突解决方法：

1.开放寻址法：

优点：1.可以有效利用CPU缓存加快查询速度。

2.序列化起来简单。

缺点：1.删除数据比较麻烦

2.冲突的代价更高

当数据量小、装载因子小的时候，适合采用开放寻址法。这也是java中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。



2.链表法

优点：

1.链表法对内存的利用率比开放寻址法要高。

2.链表法比起开放寻址法，对大装载因子的容忍度更高。

缺点：

1.链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的。

2.链表中的结点是零散分布在内存中的，不是连续的，所以对CPU缓存是不友好的。



更高效的散列表实现，将链表法中的链表改造为其他高效的动态数据结构，比如跳表，红黑树。这样，即使出现散列冲突，极端情况下，所以的数据都散列到同一个桶内，那最终退化成散列表的查找时间也不过是O(logn).这样也就有效避免了散列碰撞攻击。

基于链表的散列冲突处理方法比较适合存储大对象大数据量的散列表，而且比起开放寻址法，它更加灵活，支持更多的优化策略。比如用红黑树代替链表。



工业级散列表分析：HashMap



1.初始大小 16

2.装载因子和动态扩容 0.75

3.散列冲突的解决方法 链表法 JDK1.8中引入了红黑树，默认链表长度超过8时，就转换为红黑树。--这个解释的很清楚，之前了解的不深入、

4.散列函数

int hash(Object key) {

int h = key.hashCode()；

return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小

}

何为一个工业级的散列表？工业级的散列表有哪些特性？

1.支持快速查询、插入、删除操作。

2.内存占用合理。不能浪费过多的内存空间。

3.性能稳定，极端情况下，散列表的性能不会退化到无法接受的情况。

如何实现这样一个散列表：

1.设计一个合适的散列函数。

2.定义装载因子阈值，并且设计动态扩容策略。

3.选择合适的散列冲突解决方法。



散列表和链表是如何组合起来使用的，为什么散列表和链表会经常放在一起使用。



LRU缓存淘汰算法：坐着借鉴了HashTable的思路

Redis有序集合

LindedHashMap添加元素的时候，会删除已存在的相同的Key的值

为什么散列表和和链表经常一起使用?



散列表虽然支持非常高效的数据插入，删除，查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律储存的。无法按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据。那我们需要将散列表中的数据拷贝到数组中，然后排序，再遍历。因为散列表是动态数据结构，不停地有数据的插入，删除，所以每当希望按顺序遍历散列表中的数据的时候，都需要先排顺序，那效率势必会很低。为了解决这个问题，将散列表和链表结合在一起使用。



哈希算法：

在实际开发中，该如何用hash算法解决问题？

hash算法的应用：

1. 安全加密

2. 唯一标识 搜索一张图片是否存在

3. 数据校验 校验文件块的正确 安全 完整

4. 散列函数

5. 负载均衡

6. 数据分片

7. 分布式存储

哈希算法在分布式系统中的应用：

负载均衡：

实现会话粘滞的负载均衡算法：在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。

通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得到的哈希值与服务器列表的大小进行取模运算，最终得到的值就是被路由的服务器编号



应用六：数据分片



二叉树





二叉树：

1.满二叉树

2.完全二叉树



存储二叉树的两种方法：

1.基于指针或者引用的二叉链式储存法 每个节点有3个字段，其中一个存储数据，另外两个是指向左右子节点的指针



2.基于数组的顺序存储法

把根节点存储在下标i=1的位置，左子节点存储在下标2*i=2的位置

右子节点存储在2*i+2的位置。B节点的左子节点存储在2*i=2*2=4的位置

（这个设计太巧妙了）

非完全二叉树：

二叉树的遍历：

1.前序遍历 对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

2.中序遍历 先打印左子树，在打印它本身，最后打印右子树

3.后序遍历 先打印左子树，再打印右子树，最后打印这个节点本身。



二叉查找树：支持动态数据集合的快速插入、删除、查找操作

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值



1.二叉树的查找操作



先取根节点，如果它等于要查找的数据，就返回，如果要查找的数据比根节点值小，就在左子树中递归查找，如果要查找的数据比根节点的值大，那就在右子树中递归查找。



2.二叉树的删除操作



1.如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指针置为null

2.如果要删除的节点只有一个子节点，只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。

3.如果要删除的节点有两个子节点。需要找到这个节点中右子节点中的最小节点，把它替换到要删除的节点上，然后再删除掉这个最小节点。



中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(n),非常高效。



支持重复数据的二叉查找树



散列表的插入、删除，查找操作的时间复杂度可以做到常量级的O(1)，非常高效，而二叉查找树在比较平衡的情况下，插入，删除，查找操作时间复杂度才是O(logn),相对散列表，好像并没有什么优势，那为什么还要使用二叉查找树呢？

1.散列表中的数据是无序存储的

2.散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定。

3.因为哈希冲突的存在，这个常量并不一定比logn小

4.散列表的构造比二叉查找树要复杂

5.为了避免过多的散列冲突，散列表装载因子不能太大。



红黑树

为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树？

很多平衡二叉树在大部分情况下，操作的效率都很高，但是也无法避免极端情况下时间复杂度的退化。尽管这种情况出现的概率不大，但是对于单次操作时间非常敏感的场景来说，它们并不适用。

AVL树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL树为了维持这种高度的平衡，就要付出更多的代码，每次插入，删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入，删除操作的数据集合，使用AVL的代价有点高。红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比AVL树要低。所以红黑树的插入，删除，查找各种操作性能都比较稳定。



平衡二叉树：二叉树中任意一个节点的左右子树的高度相差不能大于1



发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入，删除等动态更新的情况下，出现时间复杂度退化的问题。



红黑树的要求：

1. 一类被标记为黑色，一类被标记为红色

2. 根节点是黑色的

3. 每个叶子节点都是黑色的空节点

4. 任何相邻的节点都不能同时为红色

5. 每个节点，从该节点到达其他叶子节点的所有路径，都包含相同数目的黑色节点。

左右旋 平衡调整



红黑树的插入，删除操作会破坏红黑树的定义



插入操作的平衡调整：

红黑树规定，茶放入的节点必须是红色的，而且二叉查找树中新插入的节点都是放在叶子节点上。

正在处理的节点叫做关注节点，关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。

删除部分看不下去了，云里雾里

递归树

实战一：分析快速排序的时间复杂度

实战二：分析斐波那契数列的时间复杂度

实战三：分析全排列的时间复杂度

用递归树分析，确实省事多了，但是对于实战的理解还不透彻



堆和堆排序：

1.堆是一个完全二叉树

2.堆中的每个节点的值都必须大于等于（小于等于）其子树中每个节点的值。



1.往堆中插入一个元素 堆化

2.删除堆顶元素

堆排序的过程大致分为 建堆和排序

这一节又是云里雾里的



堆的应用：

1.优先级队列

2.求TopK

3.求中位数



一个堆可以看作一个优先级队列

1.合并有序小文件 没看懂思路

2.高性能定时器