2018.2.14 algo part2 heaps and trees

1.

先讲的堆，其实上周的dijkstra就有涉及到堆的内容，但是这周才详细的讲堆本身。堆逻辑上是一个二叉树，父节点的值比两个子节点都要大（或者比两个小）。堆是一个完全二叉树，所以很适合直接就用数组表示，因为父节点和字节点的位置关系是确定的（2n和2n+1）。

堆的特点是它一直把最大/最小值放在根节点，因此如果你的需求是需要不停的对一组动态的数据求max/min，那么你就可以用堆来优化。当然，除了extract min/max以外一般还需要同时做插入数据之类的操作，否则就是静态数据了，如果是静态数据直接数组就行了。

（1）对一个排好的堆做insert操作，就是把插入的数据放在堆的最末尾，然后看它是不是比父节点小（假设是min堆），如果是就没啥问题，不是的话就和父节点交换（把父节点挤下来）然后再和新的父节点比，直到比父节点小为止。这个动作很显然是O（lg n）的。

（2）另外一个常用操作就是extract min了，毕竟这就是堆的本职工作。步骤是把根节点pop掉后，用尾部的结点代替根节点。当然这时候的堆显然不太对，所以新的根节点需要不停的和自己比较小的子节点交换，直到没有子节点，或者比所有子节点都小为止。这个动作也是O（lg n）的。

一般来说，heap做的操作时间复杂度看起来和二叉树差不多，而且heap还不能同时保存min和max，而二叉树却可以。但是heap的优势是，大部分操作heap的时间复杂度常数以及空间复杂度都要更好些。

2.

下一个话题就是二叉树了，或者具体说是平衡二叉搜索树。对于数据结构来说，一个排好的数组看起来已经很强大了，但是它很难处理动态的数据，因为它的插入或删除操作很可能是O（n），这就比较僵硬。所以当你需要频繁插入或删除的时候，就需要使用平衡二叉树，来得到O（lg n）的性能。

先说普通非平衡的二叉搜索树，二叉搜索树的特征就是对于父节点来说，左边子树的所有值都比它小，而右边子树都更大。对这样的树搜索，自然非常方便，从根节点搜起，左拐右拐就拐到了。insert的话其实和search一样，就是先search你要插入的那个数据，然后把数据插进search到的应该出现的位置就对了。

（1）求max或者min，就是从根节点找起，一直向左拐或者一直向右拐，直到到头为止，很简单很直观。

（2）找某个结点的数值上的前一个结点：如果该结点有左子树，那么找到左子树的max结点；如果左子树是空的，那么就顺着父节点向上爬，爬到第一个比它小的就是他的前一个结点了。找数值上的后一个结点也一样，把左右颠倒下就行。

（3）把二叉搜索树输出为有序数组：一个大量递归的算法。对于给定的根节点，先对他的左子树递归这个算法，然后打印根节点，然后对右子树递归这个算法。这里应该需要一个判定条件，如果只有一个子树就递归这个子树就好。没有子树就是base case，直接打印叶子结点。

（4）对二叉搜索树的结点做删除操作：如果是叶子，直接删掉就好。如果该结点只有一个子树，那么把他删掉，然后把他的父节点和子树连上就行。如果是两个子树都有，就比较麻烦，需要找出他左子树的max结点，然后把max结点和待煽节点交换，交换后待删结点是只有左子树或者没子树的，那么用前面两个方法之一处理就好。

（5）对二查搜索树做select操作：就是找出该树第i大的数据。对这种操作，我们需要一个辅助数据，就是我们要知道每个节点的size。size就是这个节点的左右子树（如果有的话）连同他自己的所有结点的数量。求一个节点的size显然用递归就好，比较简单。不过insert和delete操作之后需要对size更新，比较麻烦。

有了size之后就很简单了，从root找起，如果左子树的size刚好是i-1，那就是root了；如果左子树的size比i-1大，那么对左子树递归；如果比i-1小，那么对右子树递归，不过要找的序数i要调整，有点像之前的R-selection算法。