《数据结构与算法之美》基础篇笔记（四）

2020-12-25

摘要：极客时间《数据结构与算法之美》基础篇笔记，二叉树、红黑树、递归树、堆及堆排序

树 Tree

树是一种非线性的数据结构,是由 n(n>=0) 个节点组成的有限集合。
Tree
如上图，A 节点是 B、C、D 节点的父节点，B、C、D 节点是 A 节点的子节点，D、C、D 互为兄弟节点。E 节点没有父节点，被称为根节点，G、H、I、J、K、L 没有子节点，都被称为叶(子)节点
TreeHeight
如上图，高度是从下往上开始度量，从 0 开始
深度是从上往下开始度量，也是从 0 开始
层数 = 深度 + 1（对比十八层地狱记忆），根节点是第 1 层
BST树 AVL树红黑树 23树 234树 B树 B+树

二叉树 Binary Tree

二叉树，每个节点最多有两个节点，分别是左子节点和右子节点。当除叶子节点外，所有节点都有左右两个节点，这种二叉树叫满二叉树。当叶子节点只出现在最下层和次下层，且最下层的叶子节点集中在树的左部时，这种二叉树叫完全二叉树。满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树
有两种方法存储二叉树：
1、基于指针或者引用的二叉链式存储法
2、基于数组的顺序存储法
链式存储法的每个节点有三个字段：一个存储数据，另外两个存储左右两个子节点的指针。这种存储方式比较常用，如下图
Binary Tree Link
顺序存储法则是将根节点保存在下标为 i = 1 的位置上。如果节点存储在数组下标为 i 的位置上，那么它的左子节点存储在下标为2*i的位置上，右子节点则存储在下标为2*i+1的位置上。如下图：
Binary Tree Array
使用数组保存完全二叉树是最节省内存的一种方式，因为不用存储左右子节点指针，而且除了第一个下标为 0 的位置是空的，其他位置都是有元素的。而非完全二叉树则会浪费比较多的数组存储空间:2*i+1的位置上会有一部分是空的。

遍历二叉树

遍历二叉树有三种经典的方法：
1、前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
2、中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
3、后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印它本身。
Binary Tree Bianli
前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序，而其遍历就是一个递归的过程，遍历的时间复杂度是 O(n)。在二叉树中序遍历的序列中，一个节点的前一个节点叫该节点前驱节点，后一个节点叫该节点后继节点
还有层序遍历，就是一层一层的遍历，从第 1 层开始遍历。
这里要用到的辅助数据结构是队列，利用队列先进先出的性质：创建一个队列，先将根节点入队，再将根节点出队，打印出队节点的值，接下来看出队的节点（也就是刚才的根节点）有没有左子节点或右子节点，如果有，先左后右入队，只要队列还不为空，就说明还没有遍历完，就进行下一次循环。这时的队头元素则为刚才入队的左子节点，然后该节点出队，打印出队节点的值，再把它的左右子节点拉进来（如果有）。这样循环往复，当队列为空时，整颗树就层序遍历完成了，结束循环

二叉查找树 Binary Search Tree (BST)

二叉查找树也叫二叉搜索树，它最大的特点就是支持动态数据集合的快速插入、删除、查找操作。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
1、查找操作：先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找
2、插入操作：从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置
3、删除操作：删除操作比较麻烦，因为删除节点还要考虑它有没有子节点。如果没有子节点，只需要将指向要删除节点的指针设置为 null 即可；如果有一个子节点，将原本指向要删除节点的指针指向子节点就行；但如果有两个子节点，需要找到要删除节点的后继节点（大于删除节点的最小节点），然后将后继节点数据替换到要删除的节点上并删除这个后继节点，则将删除某个节点转变成删除该节点的后继节点，而后继节点最多只可能有一个右子节点，按照前两种情况处理即可
二叉查找树的中序遍历可以输出有序的数据序列，时间复杂度为 O(n)

// 节点辅助类
class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

// 二叉查找树类
class SearchTree {
  constructor() {
    this.root = null;
  }

  // 查找
  find(data) {
    let current = this.root;
    while (current != null) {
      if (data < current.data) {
        current = current.left;
      } else if (data > current.data) {
        current = current.right;
      } else {
        return current;
      }
    }
    return null;
  }

  // 插入
  insert(data) {
    if (this.root == null) {
      this.root = new Node(data);
      return;
    }
    let current = this.root;
    while (current != null) {
      if (data > current.data) {
        if (current.right == null) {
          current.right = new Node(data);
          return;
        }
        current = current.right;
      } else { // data < current.data 
        if (current.left == null) {
          current.left = new Node(data);
          return;
        }
        current = current.left;
      }
    }
  }

  // 删除
  delete(data) {
    let current = this.root; // current 是要删除的节点，初始化指向根节点 
    let node = null; // node 记录的是 current 的父节点 
    while (current != null && current.data != data) {
      node = current;
      if (data > current.data) {
        current = current.right;
      } else {
        current = current.left;
      }
    }
    // 没有找到
    if (current == null) return;
    // 要删除的节点有两个子节点 
    if (current.left != null && current.right != null) { // 查找右子树中最小节点
      let minRightCurrent = current.right;
      let minRightNode = current; // minRightNode 表示 minRightCurrent 的父节点 
      while (minRightCurrent.left != null) {
        minRightNode = minRightCurrent;
        minRightCurrent = minRightCurrent.left;
      }
      current.data = minRightCurrent.data; // 将 minRightCurrent 的数据替换到 current 中
      // 此时数据已替换，下面就变成删除 minRightCurrent
      current = minRightCurrent;
      node = minRightNode;
    }
    // 删除节点没有子节点或者仅有一个子节点
    let child = null; // current 的子节点，默认没有子节点
    if (current.left != null) { // 仅有左子节点
      child = current.left;
    } else if (current.right != null) { // 仅有右子节点
      child = current.right;
    }
    if (node == null) {
      this.root = child; // 删除的是根节点 
    } else if (node.left == current) {
      node.left = child;
    } else {
      node.right = child;
    }
  }

  // 前序遍历（递归）
  preOrder(node) {
    if (node == null) return;
    // 先打印本身
    console.log(node.data)
    // 后打印左子树
    this.preOrder(node.left);
    // 最后打印右子树
    this.preOrder(node.right);
  }

  // 前序遍历（非递归）
  preOrder2(node) {
    if (node == null) return;
    let nodesList = [node]; // 维护一个栈，先进后出
    let resList = []
    while (nodesList.length) {
      let current = nodesList.pop();
      resList.push(current)
      // 右子树要先入栈，这样才能后出栈
      if (current.right) nodesList.push(current.right);
      if (current.left) nodesList.push(current.left);
    }
    return resList
  }

  // 中序遍历（递归）
  inOrder(node) {
    if (node == null) return;
    this.inOrder(node.left);
    console.log(node.data)
    this.inOrder(node.right);
  }

  // 中序遍历（非递归）
  inOrder2(node) {
    if (node == null) return;
    let nodesList = [node] // 维护一个栈，先进后出
    let current = node
    let resList = []
    while (nodesList.length > 0) {
      while (current && current.left) {
        current = current.left;
        nodesList.push(current);
      }
      current = nodesList.pop();
      resList.push(current);
      if (current.right) nodesList.push(current.right);
      current = current.right;
    }
    return resList
  }

  // 后序遍历（递归）
  pastOrder(node) {
    if (node == null) return;
    this.pastOrder(node.left);
    this.pastOrder(node.right);
    console.log(node.data)
  }

  // 后序遍历（非递归）
  pastOrder2(node) {
    if (node == null) return;
    let nodesList = [node]; // 维护一个栈，先进后出
    let resList = [];
    while (nodesList.length) {
      let current = nodesList.pop();
      resList.push(current);
      if (current.left) nodesList.push(current.left);
      if (current.right) nodesList.push(current.right);
    }
    return resList.reverse();
  }

  // 层序遍历
  levelOrder(node) {
    if (node == null) return;
    let nodesList = [node]; // 维护一个队列，先进先出
    let resList = [];
    while (nodesList.length) {
      const current = nodesList.shift();
      resList.push(current);
      if (current.left) nodesList.push(current.left);
      if (current.right) nodesList.push(current.right);
    }
    return resList;
  }

  // 获取高度（递归）
  getHeight(node) {
    if (node == null) return 0;
    let left = this.getHeight(node.left);
    let right = this.getHeight(node.right);
    return left > right ? left + 1 : right + 1;
  }

  // 获取高度（非递归）
  getHeight2(node) {
    if (node == null) return 0;
    let nodesList = [node]; // 维护一个队列，先进先出
    let length = nodesList.length; // 树每层添加的节点数
    let num = 0; // 用于记录每层已经遍历节点的个数
    let height = 1; // 高度
    while (nodesList.length) {
      const current = nodesList.shift();
      num++;
      if (current.left) nodesList.push(current.left);
      if (current.right) nodesList.push(current.right);
      if (length == num && nodesList.length) { // 如果每层添加的节点数已经遍历完，而且队列中还有数据，说明下一层还有数据
        height++;
        num = 0;
        length = nodesList.length;
      }
    }
    return height;
  }

  // 最大节点：右遍历到底
  findMax() {
    if (this.root == null) return null;
    let current = this.root;
    while (current.right != null) {
      current = current.right;
    }
    return current.data;
  }

  // 最小节点：左遍历到底
  findMin() {
    if (this.root == null) return null;
    let current = this.root;
    while (current.left != null) {
      current = current.left;
    }
    return current.data;
  }

  // 前驱节点：找到当前节点，如果有左子树，则对其左子树进行向右遍历到底；如果没有左子树，需要记录出栈的历史
  findPrev(data) {
    let current = this.find(data)
    if (current == null) {
      return null
    }
    // 有左子树
    if (current.left != null) {
      current = current.left
      while (current.right != null) {
        current = current.right;
      }
      return current
    } else {
      let nodesList = [this.root] // 维护一个栈，先进后出
      current = this.root
      let resList = [] // 中序遍历的数组
      let loop = true // 找到前驱节点暂停遍历的标识
      while (nodesList.length > 0 && loop) {
        while (current && current.left) {
          current = current.left;
          nodesList.push(current);
        }
        current = nodesList.pop();
        resList.push(current)
        // 判断是否是目标节点，如果是，那么中序遍历数组 resList 的最后一个元素即是目标节点的前驱节点。但目标节点有可能是中序遍历的第一个元素，此时 resList 长度为 1，它没有前驱节点
        if (current.data == data) {
          loop = false
          break;
        }
        if (current.right) nodesList.push(current.right);
        current = current.right;
      }
      // 有目标节点且目标节点不是中序遍历数组 resList 的第一个元素
      if (!loop && resList.length > 1) return resList[resList.length - 2]
      return null
    }
  }

  // 后继节点：找到当前节点，如果有右子树，对其右子树进行向左遍历到底；如果没有右子树，需要记录出栈的历史
  findNext(data) {
    let current = this.find(data)
    if (current == null) {
      return null
    }
    // 有右子树
    if (current.right != null) {
      current = current.right
      while (current.left != null) {
        current = current.left;
      }
      return current
    } else {
      let nodesList = [this.root] // 维护一个栈，先进后出
      current = this.root
      let resList = [] // 中序遍历的数组
      let loop = true // 找到后继节点暂停遍历的标识
      // 开始遍历
      while (nodesList.length > 0 && loop) {
        while (current && current.left) {
          current = current.left;
          nodesList.push(current);
        }
        current = nodesList.pop();
        resList.push(current)
        // 添加至少两个节点后，中序遍历数组 resList 的倒数第二个节点是否是目标节点，如果是，那么 resList 最后第一个节点就是目标节点的后继节点
        if (resList.length > 1 && resList[resList.length - 2].data == data) {
          loop = false
          break;
        }
        if (current.right) nodesList.push(current.right);
        current = current.right;
      }
      // 有目标节点，中序遍历数组 resList 至少有两个元素
      if (!loop) return resList[resList.length - 1]
      return null
    }
  }
}

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

二叉树节点存储的数据可以是对象，我们将对象的某个字段作为键值（key）来构建二叉查找树，对象中的其他字段叫做卫星数据。如果有多个对象键值相同的情况，可以使用链表或支持动态扩容的数组来把相同的数据都存储在同一个节点上。还有一种方法是将新插入的数据当做大于这个节点的值来处理，当然后面获取对应值时，需要注意：遇到值相同的节点，不能停止查找操作，而是继续在其右子树查找，直到遇到叶子节点才能停止，这样才能将所有键值等于要查找的值的节点找到。同样，删除操作也要遍历到相同值节点右子树的子叶节点才能停止。

二叉树的时间复杂度

二叉树的时间复杂度其实都跟树的高度成正比，也就是 O(height)，这个问题就转化成如何得到二叉树的高度。如果是满二叉树的话，总节点数n=1+2+4+...+2^(K-1)，得到 K = log(2)n + 1 ，则时间复杂度为 O(logn)。如果是完全二叉树，总节点数1+2+4+...+2^(K-2)+1<=n<=n=1+2+4+...+2^(K-1)。由等比公式可以计算得到，完全二叉树的高度 K 取值范围是 [log(2)(n+1), log(2)n + 1] (2 为底数)，即完全二叉树的高度要小于 log(2)n

二叉树与散列表

散列表的查找、插入、删除操作的时间复杂度都可以做到 O(1)
二叉树相对于散列表的优势：
1、散列表中的数据是无序的，如果要输出有序数据还需要先排序。二叉查找树只需要中序遍历就能在 O(n) 时间复杂度内输出有序序列
2、散列表扩容耗时，而且会有散列冲突，性能不稳定。平衡二叉查找树性能稳定，时间复杂度为 O(logn)
3、虽然散列表的操作时间复杂度都是常量级，但有冲突会使性能不稳定，这个耗时常量不一定比 logn 小。而且散列函数运行也要时间，整体下来散列表的性能不一定比平衡二叉查找树高
4、散列表要考虑的方面比较多，构造比较复杂。平衡二叉查找树只需要考虑平衡性的问题，而这个问题的解决方法比较固定、成熟
5、为了避免散列冲突，散列表的装载因子不能太大，尤其是基于开放寻址法解决散列冲突的散列表，这样造成一定的内存浪费

平衡二叉查找树 Balanced Binary Tree (AVL树)

平衡二叉树：二叉树中任意一个节点的左右子树的高度相差不能大于 1。严格的平衡二叉查找树同时满足平衡二叉树和二叉查找树的定义，但实际上只不要出现左子树很高、右子树很矮的情况，就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些，仍然是一个合格的平衡二叉查找树。

红黑树（R-B Tree）

红黑树是一种不严格符合定义的平衡二叉查找树，它由 2-3树（动画 | 什么是2-3树？、234树到红黑树）演变而来，明白了红黑的意义，后面的操作就比较好理解。
红黑树满足一下几点要求：
1、每个节点或者是黑色，或者是红色
2、根节点为黑色的
3、每个叶子节点都是黑色的空节点（NIL），它不存储数据
4、红色节点被黑色节点隔开，不可能出现两个连续的红色节点
5、从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点
红黑树中包含最多黑色节点的路径不会超过 log(2)n (2为底数)，所以加入红色节点之后，最长路径不会超过 2log(2)n (2为底数)，则红黑树的高度近似 2log2n，其插入、删除、查找操作的时间复杂度都是 O(logn)。。
AVL 树是一种高度平衡的二叉树，其查找效率非常高，但每次插入和删除都要维护这种高度的平衡，需要付出更多的代价。而红黑树只是近似平衡，在维护成本上要比 AVL 低，因而红黑树的插入、删除、查找各种操作性能都比较稳定。

平衡调整

调整的过程包含两种基础的操作：左右旋转和改变颜色。
左旋：以某个节点作为支点(旋转节点)，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。
右旋：以某个节点作为支点(旋转节点)，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。
左右旋转

插入操作的平衡调整

二叉查找树中新插入的节点都是放在叶子节点上，而且插入的节点必须是红色的。因为插入黑色节点会使某一条路径上多一个额外的黑色节点，这样调整比较麻烦。而添加红色节点，如果父节点也是红色，不满足红黑树第 4 条性质，但可通过旋转和改变颜色来调整
根据新节点插入的位置来区分，一共有 10 中情况。其中有两种是比较简单的：
1、插入的红黑树是空树，将插入的节点作为根节点，并把颜色设置为黑色
2、插入节点的父节点是黑色的，符合红黑树定义，直接插入即可
那么只有父节点是红色的情况下需要进行调整，根据插入新节点的位置是父节点的左或右两个位置、父节点是祖父节点的左或右两个位置、父节点的兄弟节点是红或黑两种颜色相互组合分为 8 中情况
这 8 种情况又可以分为三类：
第一类：父节点的兄弟节点为黑色，父节点是祖父节点的左子节点，新插入的节点位置是父节点的左子节点或有子节点，共 2 种情况
第 1 种情况：插入父节点的左子节点位置
插入情况1
处理：父节点变黑，然后绕父节点右旋
第 2 种情况：插入父节点的右子节点位置
插入情况2
处理：绕父节点左旋，转换成第 1 种情况，然后按照第 1 种情况继续处理

第二类：父节点的兄弟节点为黑色，父节点是祖父节点的右子节点，新插入的节点位置是父节点的左子节点或有子节点，共 2 种情况
第 3 种情况：插入父节点的右子节点位置
插入情况3
处理：父节点变黑，然后绕父节点左旋
第 4 种情况：插入父节点的左子节点位置
插入情况4
处理：绕父节点右旋，转换成第 3 种情况，然后按照第 3 种情况继续处理

第三类：父节点的兄弟节点为红色，父节点是祖父节点的左或右两个位置，新插入的节点位置是父节点的左子节点或有子节点，共 4 种情况
插入情况5
插入情况6
插入情况7
插入情况8
处理：方法都一样，将父节点变黑，祖父节点变红，然后将祖父节点当做插入的目标节点进行递归判断
总结：优先根据叔叔节点的颜色来判断，如果叔叔节点是黑色，先绕父节点旋转将红色节点都转成外侧节点，然后父节点变黑再绕祖父节点反转；如果叔叔节点是红色，将父节点和叔叔节点变黑，祖父节点变红，然后以祖父节点为目标节点递归判断情况。

删除操作的平衡调整

红黑树的删除操作分为两步骤：1、查找并删除目标节点；2、删除后自平衡
红黑树查找并删除节点与二叉树没什么区别，一共有 3 中情况：
1、若删除节点无子节点，直接删除即可
2、若删除节点只有一个子节点，用子节点替换删除节点
3、若删除节点有两个子节点，用后继节点替换删除节点，最后删除后继节点按照情况 1 或者情况 2 处理
如果删除的是红色节点，不会破坏红黑树，不需要调整。但是如果删除的是黑色节点，会使原来包含该节点的路径上黑色节点数量减少 1，那么就不满足红黑树第 5 条性质，需要进行平衡调整
删除一共有 9 种情况，如果删除的是根节点或红色节点，直接删除即可，不需要调整。剩下的根据删除节点的颜色和位置、兄弟节点的颜色及其子节点个数的不同共有 8 中情况，可以分为三类
假设要删除的节点都是父节点的左子节点，蓝色节点表示可以是红黑任意颜色节点
第一类兄弟节点是红色
第 1 种情况：父节点和兄弟节点的子节点肯定都是黑色节点
删除情况1
处理：兄弟节点变黑，父节点变红，然后绕父节点左旋

第二类：兄第节点是黑色，兄第节点有红色子节点
第 2 种情况：兄弟节点的右子节点是红色
删除情况2
处理：将父节点的颜色赋给兄弟节点，父节点和兄弟节点的右子节点变黑，然后绕父节点左旋
第 3 种情况：兄弟节点的右子节点是黑色，但左子节点是红色
删除情况3
处理：兄弟节点变红，兄弟节点的左子节点变黑，然后绕兄弟节点右旋，此时变成第 2 种情况进行处理

第三类：兄弟节点及其子节点都为黑色
删除情况4
处理：兄弟节点变红，然后将目标节点改为父节点重新判定情况进行处理。由于 50 将要删除，将兄弟节点变红后，父节点以下的树是符合红黑树的标准，但是由于黑色节点都少一个，那么父节点以上的树就要进行调整

由于树是左右对称的，当要删除的节点时父节点的右子节点时，与上面的情况类似
第一类兄弟节点是红色
第 5 种情况：父节点和兄弟节点的子节点肯定都是黑色节点
处理：兄弟节点变黑，父节点变红，然后绕父节点右旋

第二类：兄第节点是黑色，兄第节点有红色子节点
第 6 种情况：兄弟节点的左子节点是红色
处理：将父节点的颜色赋给兄弟节点，父节点和兄弟节点的左子节点变黑，然后绕父节点右旋
第 7 种情况：兄弟节点的左子节点是黑色，但右子节点是红色
处理：兄弟节点变红，兄弟节点的右子节点变黑，然后绕兄弟节点左旋，此时变成第 6 种情况进行处理

第三类：兄弟节点及其子节点都为黑色
处理：兄弟节点变红，然后将目标节点改为父节点重新判定情况进行处理

递归树

使用递归树求解时间复杂度

一、归并排序递归树：

归并排序每次都会将排序数据对半分，代价很低，时间消耗为 1。比较耗时的操作是将两个子数组合并为大数组，由上图可以看出：归并排序的递归树是一个满二叉树，每一层的合并操作时间是一样的，跟数据的总规模有关系。假设总数据为 n，只要知道树的高度就可以等到总时间，而满二叉树的高度约为 log(2)n，则可得归并排序的时间复杂度约为 O(nlogn)

二、快排排序递归树
快速排序递归树
假设每次分区 1 比 9 分，则最短路径（左子树左遍历到底）每层依次需要处理 n，n/10，n/10^2，…，1 个数据。最后一层 n/10^h=1 可得高度 h=log(10)n （10为底数）。类似的，最长路径（右子树右遍历到底）每层依次需要处理 n，n(9/10)，n(9/10)^2，…，1 个数据。最后一层 n(9/10)^h=1 可得 h=log(10/9)n（10/9为底数）。使用大 O 表示法就是 O(nlogn)

三、斐波那契数列递归树

从根节点开始，每向下一层，每个节点的数据规模可能 -1 或 -2，每次 -1 则得最长路径大约为 n，每次 -2 则得最短路径大约为 n/2。假设每次分解之后的合并操作只需一次加法运算，每次加法运算消耗的时间记作 1，那么从上往下开始依次耗时 1，2，2^2，…，第 k 层的时间消耗就是 2^(k-1)。则总耗时就是每层耗时相加，如果以最长路径 n 计算得到总耗时 1+2+2^2+…+2^(n-1)=2^n-1，如果以最短路径 n/2 计算得到 1+2+2^2+…+2^(n/2-1)=2^(n/2)-1。则时间复杂度介于 O(2^n) 和 O(2^(n/2)) 之间

四、全排列递归树
全排列问题：把 n 个数据（假如是数字 1 到 n）的所有排列都找出来。“n 个数据的排列”问题，可以分解成 n 个“n−1 个数据的排列”的子问题，f(1,2,…n) = {最后一位是1, f(n-1)} + {最后一位是2, f(n-1)} +…+{最后一位是n, f(n-1)}，如下图所示
全排列递归树
第 k 层有n*(n−1)*(n−2)*...*(n−k+1)，最后一层有n*(n−1)*(n−2)*...*2*1=!n，全部加起来是n+n*(n-1)+n*(n-1)*(n-2)+...+n*(n-1)*(n-2)*...*2*1，最后一个数为 !n，前面 n-1 个数肯定都小于 !n，因而和肯定小于n*!n。全排列的时间复杂度很高，大于 O(n!)，小于 O(n*n!)

五、1 个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？
假设细胞是现分裂再死亡，时间 n 从 0 小时开始

n=0,f(0)=1
n=1,f(1)=2
n=2,f(2)=4
n=3,f(3)=7

得到公式：f(n)=f(n-1)x2-f(n-3)，但当 n=4 时，f(4)=2*f(3)-f(1)=12，很明显这个是错误的。因为当 n>=4 时，死亡的个数应该是 n-3 时新生的细胞个数，而 f(n-3) 得到的是 n-3 时所有的细胞，其中一些老细胞在 n-1 时就死了。n-3 时新生的细胞个数就是 n-4 时的细胞总数，所以公式应为：f(n)=2*f(n-1)-f(n-4)。如果将一次乘法和一次减法一起看做是一次基本操作，那么树的情况跟斐波那契数列递归树很相似，最高的树有 n 层，时间复杂度为 O(2^n)

堆（Heap）

堆是一种特殊的树：一个完全二叉树，堆中的每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。也就是说，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。每个节点的值都大于等于其子树节点的值得堆叫“大顶堆”，每个节点的值都小于等于其子树节点的值的堆叫“小顶堆”。完全二叉树比较适合使用数组来存储，数组中下标为 i 的节点的左子节点就是下标为i*2的节点，右子节点就是下标为i*2+1的节点，父节点就是下标为 i/2 的节点。
堆在插入或删除元素后，调整使其重新满足堆的特性，这个调整的过程叫做堆化。堆化有两种方法，从下往上和从上往下，就是顺着节点所在的路径，向上或者向下，对比，然后交换。
假设大顶堆在存储的数组最后插入一个新元素，让新元素与其父元素进行比较，如果新元素的值大于父元素的值就互换两个节点，一直重复这个过程，直到父元素的值大于新元素的值。这个是从下往上的堆化过程。

public class Heap {
  private int[] a; // 数组，从下标 1 开始存储数据
  private int n;  // 堆可以存储的最大数据个数
  private int count; // 堆中已经存储的数据个数

  public Heap(int capacity) {
    a = new int[capacity + 1];
    n = capacity;
    count = 0;
  }

  public void insert(int data) {
    if (count >= n) return; // 堆满了
    ++count;
    a[count] = data;
    int i = count;
    while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化，不断与自己的父元素比较
      swap(a, i, i/2); // swap()函数作用：交换下标为 i 和 i/2 的两个元素
      i = i/2; // 将父元素设置为目标元素
    }
  }
 }

堆顶元素存储的数据就是该堆中的最大值或最小值，如果我们删除一个节点，然后把数组最后一个节点移到删除节点的位置上，然后将该节点与其子节点进行比较，不满足父子节点大小关系的就行互换，一直重复这个过程，直到父节点大于子节点。这个是从上往下的堆化过程。

public void removeMax() { // 删除大顶堆最大值，即删除数组第一个元素
  if (count == 0) return -1; // 堆中没有数据
  a[1] = a[count]; // 将最后一个元素赋给要删除的节点，删除其他元素时与其相似，将最后一个元素赋给要删除的元素
  --count; // 删除最后一个节点
  heapify(a, count, 1);
}

private void heapify(int[] a, int n, int i) { // 自上往下堆化
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2; // 父元素与左子元素比较，找到大值下标
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1; // 在与右子元素比较，找出大值下标
    if (maxPos == i) break; // 如果下标没有变，说明父元素都大于子元素，堆化完成
    swap(a, i, maxPos); // 交换数组 a 中下标为 i 和 maxPos 两个元素
    i = maxPos; // 将子元素设置为目标元素，一直向下循环这个过程
  }
}

一个有 n 个节点的完全二叉树，其高度不会超过 log(2)n （2 是底数），而堆化的过程是顺着节点的路径来比较交换的，则堆化的时间复杂度为 O(logn)。堆的插入和删除的主要逻辑就是堆化，因而堆的插入和删除一个元素的时间复杂度都是 O(logn)

堆排序

堆排序是一种时间复杂度为 O(nlogn) 的原地排序算法。堆排序可以分为两步：建堆和排序
1、建堆
建堆有两种思路：
第一种是假设起初堆中只有一个数据，然后调用前面的插入操作，将 2 到 n 的数据插入到堆中，从下往上堆化；
第二种是从后往前处理数据，数据从上往下堆化

// 第二种
private static void buildHeap(int[] a, int n) {
  for (int i = n/2; i >= 1; --i) {
    heapify(a, n, i);
  }
}

private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

循环之所以从 1 到 n/2，是因为完全二叉树中下标从 n/2+1 到 n 的节点都是叶子节点，不需要堆化。前面有说明下标为 i 的节点，其父节点就是下标为 i/2 的节点。如果下标最大索引为 n，那么其父节点的索引就是 n/2。
建堆的时间复杂度为 O(n)，总时间是树中每层节点个数与到达该层堆化所需时间乘积的总和，而每层的堆化时间（对比交换次数）又与该层的高度有关，且子叶结点不需要堆化。
heap
推导过程：

1
2
3

S1=2^0*h+2^1*(h-1)+2^2*(h-2)+...+2^(h-1)*1
S2=      2^1*h    +2^2*(h-1)+...+2^(h-1)*2+2^h*1 // 数列各项有一个等比数列和等差数列的对应乘积构成，利用错位相减法，各项乘以公比后错位相减
S=S2-S1=-h+2^1+2^2+...+2^h

数列后面公比为 2，利用等比公式可以得到

1	S=-h+(2^1-2^h*2)/(1-2)=2^(h+1)-h-2

h=log(2)n (2为底数)，带入公式的到

1	S=2n+log(2)n-2

则得到建堆的时间复杂度为 O(n)

2、排序
建堆过后，整个数组是以大顶堆的特性来排序的。此时，我们将第一元素也就是最大的值与最后一个元素互换，然后通过堆化将数组剩下的 n-1 个元素排序。再将此时堆顶的元素与下标为 n-1 的元素互换，再次将剩下的 n-2 个元素堆化。不断重复这个过程，直到堆中只剩下下标为 1 的元素

// n：数据的个数，a：数据从下标 1 到 n 的位置
public static void sort(int[] a, int n) {
  buildHeap(a, n); // 先建堆
  int k = n;
  while (k > 1) {
    swap(a, 1, k); // 交换下标 1 和 k 两个元素
    --k; // 控制数组中堆化最大值
    heapify(a, k, 1); // 堆化数组下标 1 到 k 的元素
  }
}

堆排序建堆和排序两个过程，建堆时间复杂度为 O(n)，排序的过程类似于堆删除元素，需要删除 n 个元素，则堆排序的时间复杂度为 O(nlogn)。整个堆排序的过程中，都只需要个别临时存储空间，所以堆排序是原地排序。但堆排序在排序的过程中会将最后一个元素与堆顶元素互换，有可能改变相同值的相对位置，因而堆排序是不稳定的排序算法。
堆排序的性能没有快速排序高：
1、堆排序数据访问的方式没有快速排序友好。堆排序的访问都是跳着来的，下标跳跃幅度大，cpu 命中缓存的命中率就比较低，这就需要频繁地访问内存。而快速排序的数据是局部顺序访问，缓存按块读取数据，再次访问读入次数发生的概率会比较低。
2、堆排序算法的数据交换次数要多于快速排序。建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度降低，而快速排序的交换次数不会比逆序度多

// 大顶堆
class Heap {
  constructor(originArray = [null]) {
    this.originArray = originArray
    this.buildHeap() // 初始化时建堆
  }

  // 建堆
  buildHeap() {
    const arr = this.originArray
    const startIndex = arr.length
    for (let i = startIndex; i >= 1; i--) {
      this.heapify(arr, arr.length, i)
    }
    return arr
  }

  // 堆化
  heapify(arr, len, i) {
    while (true) {
      let maxPos = i
      if (i * 2 <= len && arr[i] < arr[i * 2]) maxPos = i * 2
      if (i * 2 + 1 <= len && arr[maxPos] < arr[i * 2 + 1]) maxPos = i * 2 + 1
      if (maxPos === i) break
      this.swap(arr, i, maxPos)
      i = maxPos
    }
  }

  // 交换位置
  swap(arr, i, max) {
    let temp = arr[i]
    arr[i] = arr[max]
    arr[max] = temp
  }

  // 插入
  insert(value) {
    const arr = this.originArray
    arr.push(value)
    let len = arr.length - 1;
    let index = Math.floor(len / 2)
    while (index > 0 && arr[len] > arr[index]) { // 自下往上堆化，不断与自己的父元素比较
      this.swap(arr, len, index);
      len = index;
      index = Math.floor(len / 2)
    }
  }

  // 删除堆顶最大元素
  removeMax() {
    const arr = this.originArray
    if (arr.length === 1) return null
    let len = arr.length - 1
    arr[1] = arr[len];
    arr.length = len
    len--
    this.heapify(arr, len, 1)
  }

  // 排序
  sort() {
    // const arr = this.buildHeap() // 先建堆，初始化时已经建堆
    const arr = [].concat(this.originArray) // 不改变原始数据，方便测试
    let len = arr.length - 1
    while (len > 1) {
      this.swap(arr, 1, len) // 交换顶元素和最后一位，堆顶元素永远是最大的
      len--
      this.heapify(arr, len, 1) // 剩下的元素重新建堆 直到 len === 1 停止
    }
    console.log(arr)
  }
}

堆的应用

一、优先级队列
在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队。用堆来实现的优先级队列是最高效的，因为堆与优先级队列非常相似，一个堆就可以看做一个优先级队列。
1、合并有序小文件
假设有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。现在需要将这些小文件合并到一个大文件中，就需要用到优先级队列。
将每个文件的第一个字符串取出放到一个数组中，然后比较大小，选择最小的放到大文件中，并将其从数组中删除，之后再次从字符串原来小文件中取出第一个字符串补充到数组中。不断循环这个过程，直到所有数据都转移到大文件为止。如果只是使用数组来存储数据，那么每次都需要遍历才能确定最小字符串，而使用堆则可以快速排序。这里使用小顶堆，堆顶即优先级队列队首，也就是最小值。不断的将小文件中的数据插入堆和删除堆顶元素，直到将所有小文件数据整合到大文件中。堆的插入和删除时间复杂度都是 O(logn)，总数 n 为 100，这比遍历数组的方式更高效。
2、高性能定时器
假设有一个定时器，这个定时器中维护了很多定时任务。如果每间隔一个很小的单位时间进行一遍任务扫描，判断是否有任务到达预定的执行时间。如果这个小的时间单位是 1 秒，那么没秒就要遍历一次任务列表，而且如果预定的时间离现在还有很长时间，那么会有大量无效的扫描。但如果将任务按预定执行的时间存储在优先级队列中，队首即小顶堆的堆顶就是最先执行的任务，只需要拿当前时间与堆顶元素的时间相减，就能得到执行时间间隔。到达预定时间间隔后执行堆顶任务，然后在计算新堆顶元素的时间间隔，这样不需要每隔 1 秒就轮询，也不需要遍历任务列表，性能更好。

二、求 Top K
两类 Top K 问题：1、静态数据集合，数据不会增减；2、动态数据集合，数据量会发生改变
1、静态数据集合，在包含 n 个数据的数组中，找到前 K 大的数据
维护一个大小为 K 的小顶堆，顺序遍历数组与堆顶元素进行比较。如果比堆顶元素大，将堆顶删除并将这个元素插入到堆中，遍历完数组后，这个堆保存的即是数组的前 K 大元素。遍历数组的时间复杂度为 O(n)，一次堆化的时间复杂度为 O(logK)，最坏情况下每个元素都入堆一次，时间复杂度为 O(nlogK)
2、动态数据集合，当数组元素不断增加时，找到前 K 大的数据
同样是维护一个 K 大小的小顶堆，先遍历数组的基础数据，构建好小顶堆后，每当有数据添加到数组，就先与堆顶的元素进行比较，大的留在堆中小的舍去。
问题：假设现在有一个包含 10 亿个搜索关键词的日志文件，如何使用 1GB 内存快速获取到 Top 10 最热门的搜索关键词
解决：内存有限，无法一下将多有数据加载，因而要先将数据分片。使用哈希算法将 10 亿条数据分片到 10 个文件（如果感觉不够可以在多分几个文件），利用散列表和堆分别求出每个文件的 Top 10，然后将这 10 个 Top 10 放在一起获得出现次数最多的 10 个关键词

三、求中位数
中位数就是处在中间位置的那个数。如果是静态的数据集合，可以先排序，第 n/2 个数据就是其中位数。但是动态的数据集合，其中位数在变化，每次获取中位数都排序的话效率很低。
维护一个大顶堆和一个小顶堆，各负责存储一半的数据，且小顶堆的数据都大于大顶堆。如果有 n 个数据，n 为偶数，则前 n/2 个数据存储在大顶堆，后 n/2 个数据存储在小顶堆；如果 n 为奇数，那么前 n/2+1 个数据放在大顶堆，后 n/2 个放在小顶堆。数据是动态变化的，如果新增的数据小于大顶堆堆顶的元素，就将其插入到大顶堆，否则，插入到小顶堆中。数据的增减会使两个堆数据的个数发生改变，不再满足各自存储一半数据的情况，此时我们可以将一个堆的堆顶元素移动到另一个堆中，即较多数据的堆将堆顶元素删除，然后较少元素的堆插入该元素，直到各自存储一半数据。
不只是求中位数，还可以快速求其他百分位的数据。中位数相当于求 50% 的数据，求 80 百分位数大于就是第n*80%个数据，类似的，大顶堆保存n*80%个数据，小顶堆保存n*20%个数据。插入新数据时，先与大顶堆堆顶元素比较，如果数据小于堆顶元素，则插入到大顶堆，否则插入到小顶堆。插入之后需要重新判断两个堆的数据个数是否满足 80:20 的比例（如果是 99 百分位数就是 99:1），如果不符合，就将一个堆的数据移到另一个堆中，使其满足这个比例。