是什么
堆是二叉树。不是对象内存的堆。不同的概念。
本质是一个数据结构，二叉树。有一些特点的二叉树。
基于数组实现。
堆的特点
1.完全二叉树 //即只有叶子那一层，允许有空节点
2.父节点比子节点大 //弱序 正因为父节点比子节点大，基于这个，根节点始终是最大的节点。
示意图
弱序
父节点，比子节点要大。但是又不是有序二叉树。
弱序的结果
1.弹出数据
就是只有队头才是最大的，权重最高，在最上面。每次弹出数据，就是从顶点弹出。
2.排序 //当然是弱序 也就是排序完成之后，仍然是根节点才是最大的。
怎么排序？
1.删除一个节点 //插入根节点
2.插入节点 //插入数组最后一个节点到数组第一个节点(也是根节点)
把最后一个节点(即数组的最后一个节点，也是二叉树的最后一个节点)，插入到根节点(因为根节点，是空节点)
3.排序
就是拿根节点和下面的数据进行排序，一直到最合适的位置为止
插入新的数据
1.插入到数组的最后一个节点
2.排序
拿新的节点，向上排序
弱序要解决的问题，即应用场景
步骤
1.每次只删除根节点
2.删除之后，重新排序
3.如果是插入新的数据，也要重新排序
解决的问题
永远是删除根节点的数据 //即每次是删除根节点
应用场景
比如书里面提到的，1.读信的时候，根据优先级来读信2.操作系统时间片轮询程序，也是根据进程的优先级。
也就是说，只要是有优先级/权重的需求，都适合。
比如，dubbo服务的权重。
作用-堆排序？
具体怎么排？
1.插入数据的时候，弱序。//循环插入所有数据。结果是弱序。
2.删除数据 //每次删除数据，都是最大数据。这样就可以得到top N。
速度
n * logN //n是外层循环。logN是每次插入或删除数据的时候，要二分查找树。
那他和快排有什么区别呢？
快排也是logN。优势在哪里？
其他应用场景
图查找
文件压缩算法
比快排的优点是什么？
学他，是因为有优点。否则，不学。
优点
稳定性更高。//稳定性，指的是，最好和最坏情况，速度差不多。
因为堆排序是n * logN //第一个n是n个数据。第二个logN，是因为基于树的二分操作。
快排，也是n * logN //第一个也是n。第二个是logN，基于二分/划分思想，不断的递归调用。
既然速度都一样，那区别到底在哪里？刚才说了，在稳定性。
为什么会有稳定性的区别呢？
区别在于，堆排序的初始数据，是自己手动插入的。所以不可能是最坏情况。
而，快排的初始数据是准备好的。可能是倒序。这样就相当于恶化为n * n。
总结
优点肯定还是两个方面：
1.速度
2.空间
但是速度有不同的方面，可以进行优化。
空间也是。
为什么海量数据，就一定要使用堆排序？
其他的算法，都是直接在内存排序的。所以，数据量不能很多，因为内存大小有限。那怎么办？只能使用很小的内存，来排序海量数据。
比如，
10~3 = 1K
10~6 = 1M //百万级别数据
10~9 = 1G //十亿级别。这就是为什么top k问题，都是说10亿级别的数据，怎么排序？就是因为十亿级别的数据，内存已经放不下了。
解决方法
堆排序 //一次只从数据源(比如，数据库)读少量数据，然后找top K。比如top 10。
那么怎么办？就是只需要10个数据的内存，每次读的少量数据，每次即每个数据插入到堆数据结构的时候，做到两点1.插入数据2.根节点最小。//好，现在第一步，我们已经插入了10个数据到堆数据结构。
接下来，插入第11个数据，怎么办？和队头的数据比较，如果小，就丢弃。如果大，就插入新的数据，怎么插入？1.弹出当前根节点，即队头数据2.插入新的数据3.向下二分查找，把最小数据，移到跟节点，即队头。
就这样，一直到最后一个数据，那么最终堆数据结构里的数据，就是top K。
向上和向下
插入数据的时候，或者删除数据的时候，都需要重新排序。怎么排序？向上二分查找，或者向下二分查找。
向下
每次比较子数据，子数据有两个，所以比较两次。如果都比父数据大，那么还要比较两个子数据哪个大，哪个大就和哪个数据交换。
向上
只需要和父数据，比较一次。
堆的本质
堆可以被用来排序，但作用不仅仅是排序。
他本质的作用是，优先级。最高优先级的数据，先被处理。
优先级队列
二叉树堆的底层是优先级队列，也就是说，本质是优先级队列。
什么是优先级队列？
队列是先进后出。优先级队列，在先进后出的基础之上，还多了一个特性：那就是数据有序。
比如，1 2 3 ... 10 //1是队头，10是尾。1先出去。
有序
1.完全有序 //有序二叉树
2.弱序 //比如堆，只要求父节点比子节点大
本质
优先级的本质，就是有序。有顺序。这个顺序，可以是完全有序，也可以是弱序。
数据结构
用什么数据结构实现？
1.数组 //有序
2.堆 //二叉树。底层也还是仍然基于数组实现二叉树。
参考
java数据结构和算法 //非常好的一本书。浅显易懂。我认为是最好的一本数据结构和算法的书。作者已经死了。
