17. 堆 
     17.1 定义:
     17.2 堆和二叉搜索树的区别:
     17.3 堆的数组存储方式：
     17.4 堆的构建：
     17.5 堆排序（最大堆）:
     17.6 堆的应用：
18. 图：
     18.1 定义：
     18.2 图的分类：
     18.3 图的表示：
     18.4 图论算法：
     18.5 总结：

17. 堆

    17.1 定义:

        这⾥的堆和Java，C++等编程语⾔在内存中的“堆”是不⼀样的。这⾥的堆通常是⼀个可以被看做⼀棵完全⼆叉树的数组对象。堆总是满⾜下列性质：
        1. 堆中某个节点的值总是不大于或不小于其父节点的值；
        2. 堆总是⼀棵完全⼆叉树。
        常见的堆有⼆叉堆(最大堆，最小堆)、斐波那契堆等。

    17.2 堆和二叉搜索树的区别:

        节点的顺序：在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。

        内存占用：普通树需要存储左右指针和数据对象。但是堆不需要存储指针

        平衡性：二叉搜索树必须是“平衡”的情况下，大部分操作的复杂度才能达到O(log n)，堆则不需要考虑平衡性

        搜索：二叉树中搜索会很快，但是在堆中搜索会很慢（堆是无序的）

    17.3 堆的数组存储方式：

        堆常用的存储方式就是数组(节省内存空间)。并且通过数组的索引(key)来定位堆的节点位置。

        通常情况下：leftChild(key)= parent(key)* 2 + 1
                              rightChild(key) = parent(key)*2 + 2

    17.4 堆的构建：

        假设有N个元素，需要将这N个元素构建成最大堆，有两种方法来构建堆：add() 与 reheap()

        add()：将新插入的元素放在数组最后，与父节点比较位置，一层一层向上浮动（见17.5堆排序代码）
        reheap()：从数组的最后一个非叶子结点开始，逐渐向前调整，直至调整到根结点。对于每个被调整的结点，将以该结点为根的子树调整成一个子堆（代码如下图）

reheap()

    17.5 堆排序（最大堆）

    17.6 堆的应用：

        堆排序：适合处理数据量大，且更新不频繁的序列

        堆排序就是利用堆删除的方法，将第⼀个元素和最后⼀个元素交换，然后size-1，在将堆里剩下的元素进⾏堆调整，调整成⼀个新堆，⼀直到堆的size为 0。

        优点：1. 效率与快排、归并相同。时间复杂度为O(nlog2n)
                   2. 只需要O(1)的辅助空间，既最高效率又最节省空间。
                   3. 相对稳定，无论待排序序列是否有序，堆排序的效率都是O(nlog2n)不变
        缺点：1. 维护问题，每次增删改都需要维护。
                   2. 步骤麻烦，需要两个步骤（⼀个建堆，⼆是交换重新建堆）因此在小规模的序列中不合适。

        top K 问题 ：在海量数据中找出最大的前k个元素

        在大量数据中找出其中最大的前k个数：可以利用堆，先将前k个数用来建堆，剩下的依次与堆中第⼀个数比较（因为最大堆中第⼀个数最大，最小堆第⼀个数最小，这里以最小堆找前k个最大的数为例），如果遇到比小顶堆的堆顶的值大的，将它放入堆中最终的堆会是数组中最大的K个数组成的结构，再使用堆排序就可以将元素按顺序排列。

        这里注意：尤其是 那种海量的数据选出出现频率最高的数据 之类的问题，思路往往都是:分而治之/hash映射 ->hash_map统计->堆/快速排序

18 图： 

    18.1 定义：

        图（Graphics）是由顶点集合(Vertex)及顶点间的关系（边）集合（Edge）组成的⼀种数据结构，这些顶点通过⼀系列边结对（连接）

有向图（左）无向图（右）

    18.2 图的分类：

        图通常分为1. 有向图和无向图（见上图）。此外还有一些其他的分类：
        2. 无权图和带权图（对边赋予具有⼀定意义的数值，如路程、费⽤等等）
        3. 稀疏图和稠密图（有很少/多的边）
        4. 完全图（任意两个顶点之间都存在⼀条边，最稠密的图就是完全图）

    18.3 图的表示：

        邻接链表法 与 邻接矩阵法

（b） 邻接链表法（c） 邻接矩阵法

    18.4 图论算法：

        1. 拓扑排序
        2. 最短路径
        3. 最小生成树
        4. 关键路径

    18.5 总结：

        1. 图是⼀种扩展的树结构，每个结点可以指向任意的其它结点
        2. 链表是特殊的树结构，树是特殊的图结构
        3. 图这种数据结构常⽤于网络规划和路径规划等领域（交通流量，飞行航线等）