树

May 17, 2022 18983

二叉树有哪几种存储方式？什么样的二叉树适合用数组来存储？

树（Tree）

A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。没有父节点的节点叫做根节点，也就是图中的节点 E。我们把没有子节点的节点叫做叶子节点或者叶节点，比如图中的 G、H、I、J、K、L 都是叶子节点。

高度（Height）：节点到叶子结点的最长路径（边数）（树的高度 = 根节点的高度）

深度（Depth）：根节点到这个节点所经历的边得个数

层（Level）：节点的深度 + 1

二叉树（Binary Tree）

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。

满二叉树：编号 2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。

完全二叉树：编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

如何求一棵包含 n 个节点的完全二叉树的高度？

包含 n 个节点的完全二叉树中，第一层包含 1 个节点，第二层包含 2 个节点，第三层包含 4 个节点，依次类推，下面一层节点个数是上一层的 2 倍，第 K 层包含的节点个数就是 2^(K-1)。

最后一层的节点个数包含的节点个数在 1 个到 2^(L-1) 个之间（假设最大层数是 L）
1
2
n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2^(L-2)+2^(L-1)
L 的范围是[log₂(n+1), log₂n +1]

完全二叉树的层数小于等于 log₂n +1，也就是说，完全二叉树的高度小于等于 log₂n。

如何表示（或者存储）一棵二叉树？

想要存储一棵二叉树，有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。

链式存储法

每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针
顺序存储法

根节点存储在下标 i = 1 的位置

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

右子节点存储在 2 * i + 1 = 3 的位置

如果节点 X 存储在数组中下标为 i 的位置，下标为 2 i 的位置存储的就是左子节点，下标为 2 i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。

完全二叉树，用数组存储是最节省内存的一种方式

二叉树的遍历

二叉树的前、中、后序遍历就是一个递归的过程

前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码，表示打印root节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码，表示打印root节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码，表示打印root节点
}

每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数 n 成正比，也就是说二叉树遍历的时间复杂度是 O(n)

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

二叉查找树（Binary Search Tree）

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

二叉查找树的查找操作

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

public class BinarySearchTree {
  private Node tree;

  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

二叉查找树的插入操作

新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }

  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

二叉查找树的删除操作

如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指针置为 null
如果要删除的节点只有一个子节点（只有左子节点或者右子节点），只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了
如果要删除的节点有两个子节点，需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了）

public void delete(int data) {
  Node p = tree; // p指向要删除的节点，初始化指向根节点
  Node pp = null; // pp记录的是p的父节点
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 没有找到

  // 要删除的节点有两个子节点
  if (p.left != null && p.right != null) { // 查找右子树中最小节点
    Node minP = p.right;
    Node minPP = p; // minPP表示minP的父节点
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 将minP的数据替换到p中
    p = minP; // 下面就变成了删除minP了
    pp = minPP;
  }

  // 删除节点是叶子节点或者仅有一个子节点
  Node child; // p的子节点
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  if (pp == null) tree = child; // 删除的是根节点
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

二叉查找树的其他操作

二叉查找树中还可以支持快速地查找最大节点和最小节点、前驱节点和后继节点

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

二叉查找树也可以存储包含很多字段的对象

利用对象的某个字段作为键值（key）来构建二叉查找树。对象中的其他字段叫作卫星数据。

问题：如果存储的两个对象键值相同，这种情况该怎么处理呢？

二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。

每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。

当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。

二叉查找树的时间复杂度分析

最坏情况时间复杂度：O(n)
最好情况时间复杂度：二叉查找树是一棵完全二叉树（或满二叉树），跟树的高度成正比，也就是 O(height)

问题：相对散列表，为什么还要用二叉查找树呢？

第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。

散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。

尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。

第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。

最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

红黑树

什么是“平衡二叉查找树”？

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。

很多平衡二叉查找树其实并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于 1）。比如红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。

如何定义一棵“红黑树”？

红黑树(Red-Black Tree，简称 R-B Tree)，是一种不严格的平衡二叉查找树。

顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

根节点是黑色的；
每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

为什么说红黑树是“近似平衡”的？

平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化得太严重。

红黑树的高度分析

首先，如果将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？

红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。

红黑树的定义中：从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。

从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树。所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。

把红色节点加回去，高度会变成多少呢？

红黑树的定义中：任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。

红黑树中包含最多黑色节点的路径不会超过 log₂n，所以加入红色节点之后，最长路径不会超过 2log₂nn，也就是说，红黑树的高度近似 2log₂n。

实现红黑树的基本思想

一棵合格的红黑树需要满足这样几个要求：

根节点是黑色的；
每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

在插入、删除节点的过程中，第三、第四点要求可能会被破坏，而红黑树的“平衡调整”，实际上就是要把被破坏的第三、第四点恢复过来。

左旋（rotate left）围绕某个节点的左旋、右旋（rotate right）围绕某个节点的右旋

插入删除平衡调整

插入操作的平衡调整

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

如果插入节点的父节点是黑色的，什么都不用做，它仍然满足红黑树的定义。
如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。
其他违背红黑树定义的情况。（左右旋转和改变颜色）

正在处理的节点叫做关注节点

如果关注节点是 a，它的叔叔节点 d 是红色

CASE 1
1. 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；
2. 将关注节点 a 的祖父节点 c 的颜色设置成红色；
3. 关注节点变成 a 的祖父节点 c；
4. 跳到 CASE 2 或者 CASE 3。
如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点

CASE 2
1. 关注节点变成节点 a 的父节点 b；
2. 围绕新的关注节点b 左旋；
3. 跳到 CASE 3。
如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点

CASE 3
1. 围绕关注节点 a 的祖父节点 c 右旋；
2. 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。
3. 调整结束。

删除操作的平衡调整

第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；第二步是针对关注节点进行二次调整，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。

针对删除节点初步调整

红黑树的定义中“只包含红色节点和黑色节点”，

经过初步调整之后，为了保证满足红黑树定义的最后一条要求，有些节点会被标记成两种颜色，“红 - 黑”或者“黑 - 黑”。如果一个节点被标记为了“黑 - 黑”，那在计算黑色节点个数的时候，要算成两个黑色节点。
1. 如果要删除的节点是 a，它只有一个子节点 b
  
  初步删除CASE 1
  1. 删除节点 a，并且把节点 b 替换到节点 a 的位置；
  2. 节点 a 只能是黑色，节点 b 也只能是红色，其他情况均不符合红黑树的定义。这种情况下，我们把节点 b 改为黑色；
  3. 调整结束，不需要进行二次调整。
2. 如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c
  
  初步删除CASE 2
  1. 如果节点 a 的后继节点就是右子节点 c，那右子节点 c 肯定没有左子树。把节点 a 删除，并且将节点 c 替换到节点 a 的位置；
  2. 然后把节点 c 的颜色设置为跟节点 a 相同的颜色；
  3. 如果节点 c 是黑色，为了不违反红黑树的最后一条定义，我们给节点 c 的右子节点 d 多加一个黑色，这个时候节点 d 就成了“红 - 黑”或者“黑 - 黑”；
  4. 这个时候，关注节点变成了节点 d，第二步的调整操作就会针对关注节点来做。
3. 如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点
  
  初步删除CASE 3
  1. 找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 CASE 1；
  2. 将节点 a 替换成后继节点 d；
  3. 把节点 d 的颜色设置为跟节点 a 相同的颜色；
  4. 如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了“红 - 黑”或者“黑 - 黑”；
  5. 这个时候，关注节点变成了节点 c，第二步的调整操作就会针对关注节点来做。
针对关注节点进行二次调整

经过初步调整之后，关注节点变成了“红 - 黑”或者“黑 - 黑”节点
1. 如果关注节点是 a，它的兄弟节点 c 是红色的
  
  删除二次调整CASE 1
  1. 围绕关注节点 a 的父节点 b 左旋；
  2. 关注节点 a 的父节点 b 和祖父节点 c 交换颜色；
  3. 关注节点不变；
  4. 继续从四种情况中选择适合的规则来调整。
2. 如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的
  
  删除二次调整CASE 2
  1. 将关注节点 a 的兄弟节点 c 的颜色变成红色；
  2. 从关注节点 a 中去掉一个黑色，这个时候节点 a 就是单纯的红色或者黑色；
  3. 给关注节点 a 的父节点 b 添加一个黑色，这个时候节点 b 就变成了“红 - 黑”或者“黑 - 黑”；
  4. 关注节点从 a 变成其父节点 b；
  5. 继续从四种情况中选择符合的规则来调整。
3. 如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色
  
  删除二次调整CASE 3
  1. 围绕关注节点 a 的兄弟节点 c 右旋；
  2. 节点 c 和节点 d 交换颜色；
  3. 关注节点不变；
  4. 跳转到 CASE 4，继续调整。
4. 如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的
  
  删除二次调整CASE 4
  1. 围绕关注节点 a 的父节点 b 左旋；
  2. 将关注节点 a 的兄弟节点 c 的颜色，跟关注节点 a 的父节点 b 设置成相同的颜色；
  3. 将关注节点 a 的父节点 b 的颜色设置为黑色；
  4. 从关注节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色或者黑色；
  5. 将关注节点 a 的叔叔节点 e 设置为黑色；调整结束。

递归树

如何用递归树，来分析递归代码的时间复杂度

归并排序递归树时间复杂度

因为每次分解都是一分为二，所以代价很低，把时间上的消耗记作常量 1。

归并算法中比较耗时的是归并操作，也就是把两个子数组合并为大数组。从图中可以看出，每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关。把每一层归并操作消耗的时间记作 n。

只需要知道这棵树的高度 h，用高度 h 乘以每一层的时间消耗 n，就可以得到总的时间复杂度 O(n * h)

归并排序递归树是一棵满二叉树。满二叉树的高度大约是 log₂n，所以，归并排序递归实现的时间复杂度就是 O(nlogn)

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

快速排序在最好情况下，每次分区都能一分为二，用递推公式 T(n)=2T(n/2)+n，很容易就能推导出时间复杂度是 O(nlogn)。但是，不可能每次分区都正好一分为二。

假设平均情况下，每次分区之后，两个分区的大小比例为 1:k。当 k=9 时，如果用递推公式的方法来求解时间复杂度的话，递推公式就写成 T(n)=T(n/10)+T(9n/10)+n。

用递归树来分析快速排序的平均情况时间复杂度

快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是 n。我们现在只要求出递归树的高度 h，这个快排过程遍历的数据个数就是 h n ，也就是说，时间复杂度就是 O(h n)。

因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。

快速排序结束的条件就是待排序的小区间，大小为 1，也就是说叶子节点里的数据规模是 1。从根节点 n 到叶子节点 1，递归树中最短的一个路径每次都乘以 1/10，最长的一个路径每次都乘以 9/10。通过计算可以得到，从根节点到叶子节点的最短路径是 log₁₀n，最长的路径是 log_10/9n

所以，遍历数据的个数总和就介于 nlog₁₀n 和 nlog_10/9n 之间

当分区大小比例是 1:9 时，快速排序的时间复杂度仍然是 O(nlogn)

对于 k 等于 9，99，甚至是 999，9999……，只要 k 的值不随 n 变化，是一个事先确定的常量，那快排的时间复杂度就是 O(nlogn)。所以，从概率论的角度来说，快排的平均时间复杂度就是 O(nlogn)。

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

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

斐波那契数列递归树的高度

f(n) 分解为 f(n−1) 和 f(n−2)，每次数据规模都是 −1 或者 −2，叶子节点的数据规模是 1 或者 2。所以，从根节点走到叶子节点，每条路径是长短不一的。如果每次都是 −1，那最长路径大约就是 n；如果每次都是 −2，那最短路径大约就是 n/2。

每次分解之后的合并操作只需要一次加法运算，把这次加法运算的时间消耗记作 1。所以，从上往下，第一层的总时间消耗是 1，第二层的总时间消耗是 2，第三层的总时间消耗就是 2²。依次类推，第 k 层的时间消耗就是 2^k−1，那整个算法的总的时间消耗就是每一层时间消耗之和。

如果路径长度都为 n，那这个总和就是 2ⁿ−1。

如果路径长度都是 n/2 ，那整个算法的总的时间消耗就是 2^n/2−1。

算法的时间复杂度就介于 O(2ⁿ) 和 O(2^n/2) 之间

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

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

如果确定了最后一位数据，那就变成了求解剩下 n−1 个数据的排列问题。而最后一位数据可以是 n 个数据中的任意一个，因此它的取值就有 n 种情况。所以，“n 个数据的排列”问题，就可以分解成 n 个“n−1 个数据的排列”的子问题。

1
2
3

假设数组中存储的是1，2， 3...n。
        
f(1,2,...n) = {最后一位是1, f(n-1)} + {最后一位是2, f(n-1)} +...+{最后一位是n, f(n-1)}。

// 调用方式：
// int[]a = a={1, 2, 3, 4}; printPermutations(a, 4, 4);
// k表示要处理的子数组的数据个数
public void printPermutations(int[] data, int n, int k) {
  if (k == 1) {
    for (int i = 0; i < n; ++i) {
      System.out.print(data[i] + " ");
    }
    System.out.println();
  }

  for (int i = 0; i < k; ++i) {
    int tmp = data[i];
    data[i] = data[k-1];
    data[k-1] = tmp;

    printPermutations(data, n, k - 1);

    tmp = data[i];
    data[i] = data[k-1];
    data[k-1] = tmp;
  }
}

第一层分解有 n 次交换操作，第二层有 n 个节点，每个节点分解需要 n−1 次交换，所以第二层总的交换次数是 n (n−1)。第三层有 n (n−1) 个节点，每个节点分解需要 n−2 次交换，所以第三层总的交换次数是 n (n−1) (n−2)。

以此类推，第 k 层总的交换次数就是 n (n−1) (n−2) … (n−k+1)。最后一层的交换次数就是 n (n−1) (n−2) … 2 * 1。每一层的交换次数之和就是总的交换次数

1	`n + n(n-1) + n(n-1)(n-2) +... + n(n-1)(n-2)...21`

最后一个数，n (n−1) (n−2) … 2 1 等于 n!，而前面的 n−1 个数都小于最后一个数，所以，总和肯定小于 n n!，也就是说，全排列的递归算法的时间复杂度大于 O(n!)，小于 O(n * n!)

“堆”（Heap）

堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法

堆排序不是稳定的排序算法

堆满足的两点要求：

堆是一个完全二叉树；
堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

如何实现一个堆？

完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。

数组中下标为 i 的节点的左子节点，就是下标为 i 2 的节点，右子节点就是下标为 i 2 + 1 的节点，父节点就是下标为 i/2 的节点。

堆化（heapify）

堆化有两种，从下往上和从上往下

从下往上的堆化方法

让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足堆的大小关系

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);
    i = maxPos;
  }
}

一个包含 n 个节点的完全二叉树，树的高度不会超过 log₂n。堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是 O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化，所以，往堆中插入一个元素和删除堆顶元素的时间复杂度都是 O(logn)。

如何基于堆实现排序？

建堆

将数组原地建成一个堆。所谓“原地”就是，不借助另一个数组，就在原数组上操作。

第一种是在堆中插入一个元素的思路。尽管数组中包含 n 个数据，假设，起初堆中只包含一个数据，就是下标为 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;
  }
}

对下标从 n/2 开始到 1 的数据进行堆化，下标是 n/2+1 到 n 的节点是叶子节点，我们不需要堆化

对于完全二叉树来说，下标从 n/2+1 到 n 的节点都是叶子节点

建堆操作的时间复杂度:

因为叶子节点不需要堆化，所以需要堆化的节点从倒数第二层开始。每个节点堆化的过程中，需要比较和交换的节点个数，跟这个节点的高度 k 成正比。

因为 h=log₂n，代入公式 S，就能得到 S=O(n)，所以，建堆的时间复杂度就是 O(n)。

排序

建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。

然后再通过堆化的方法，将剩下的 n−1 个元素重新构建成堆。堆化完成之后，我们再取堆顶的元素，放到下标是 n−1 的位置，一直重复这个过程，直到最后堆中只剩下标为 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);
    --k;
    heapify(a, k, 1);
  }
}

堆排序的时间复杂度:

整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。

问题：实际开发中，为什么快速排序要比堆排序性能好？

堆排序数据访问的方式没有快速排序友好

对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序

对于基于比较的排序算法来说，整个排序过程就是由两个基本的操作组成的，比较和交换（或移动）。快速排序数据交换的次数不会比逆序度多。

但是堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度降低。

堆的应用

优先级队列

在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队。

往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。
1. 合并有序小文件
  
  假设有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。希望将这些 100 个小文件合并成一个有序的大文件。
  
  将从小文件中取出来的字符串放入到小顶堆中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。将这个字符串放入到大文件中，并将其从堆中删除。然后再从小文件中取出下一个字符串，放入到堆中。循环这个过程，就可以将 100 个小文件中的数据依次放入到大文件中。
2. 高性能定时器
  
  假设有一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。定时器每过一个很小的单位时间（比如 1 秒），就扫描一遍任务，看是否有任务到达设定的执行时间。如果到达了，就拿出来执行。
  
  但是，这样每过 1 秒就扫描一遍任务列表的做法比较低效，主要原因有两点：第一，任务的约定执行时间离当前时间可能还有很久，这样前面很多次扫描其实都是徒劳的；第二，每次都要扫描整个任务列表，如果任务列表很大的话，势必会比较耗时。
  
  按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。
  
  定时器拿队首任务的执行时间点，与当前时间点相减，得到一个时间间隔 T。
  
  这个时间间隔 T 就是，从当前时间开始，需要等待多久，才会有第一个任务需要被执行。
  
  定时器就可以设定在 T 秒之后，再来执行任务。从当前时间点到（T-1）秒这段时间里，定时器都不需要做任何事情。
  
  当 T 秒时间过去之后，定时器取优先级队列中队首的任务执行。然后再计算新的队首任务的执行时间点与当前时间点的差值，把这个值作为定时器执行下一个任务需要等待的时间。这样，定时器既不用间隔 1 秒就轮询一次，也不用遍历整个任务列表，性能也就提高了。
利用堆求 Top K
1. 针对静态数据集合：数据集合事先确定，不会再变
  
  维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。
  
  遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，时间复杂度就是 O(nlogK)。
2. 针对动态数据集合：数据集合事先并不确定，有数据动态地加入到集合中
  
  一个数据集合中有两个操作，一个是添加数据，另一个询问当前的前 K 大数据。如果每次询问前 K 大数据，我们都基于当前的数据重新计算的话，那时间复杂度就是 O(nlogK)，n 表示当前的数据的大小。
  
  一直维护一个 K 大小的小顶堆，当有数据被添加到集合中时，我们就拿它与堆顶的元素对比。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理。这样，无论任何时候需要查询当前的前 K 大数据，我们都可以立刻返回。
利用堆求中位数

维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。

如果有 n 个数据，n 是偶数，我们从小到大排序，那前 n/2 个数据存储在大顶堆中，后 n/2 个数据存储在小顶堆中。这样，大顶堆中的堆顶元素就是我们要找的中位数。如果 n 是奇数，情况是类似的，大顶堆就存储 n/2+1 个数据，小顶堆中就存储 n/2 个数据。

如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；否则，我们就将这个新数据插入到小顶堆。

可能出现，两个堆中的数据个数不符合前面约定的情况:从一个堆中不停地将堆顶元素移动到另一个堆，通过这样的调整，来让两个堆中的数据满足上面的约定。

Trie树

Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

有 6 个字符串，它们分别是：how，hi，her，hello，so，see。希望在里面多次查找某个字符串是否存在。

对这 6 个字符串做一下预处理，组织成 Trie 树的结构，之后每次查找，都是在 Trie 树中进行匹配查找。

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。

Trie 树构造的分解过程

img

Trie 树构造的分解过程

如何实现一棵 Trie 树？

Trie 树主要有两个操作

一个是将字符串集合构造成 Trie 树。这个过程分解开来的话，就是一个将字符串插入到 Trie 树的过程。
另一个是在 Trie 树中查询一个字符串。

借助散列表的思想，通过一个下标与字符一一映射的数组，来存储子节点的指针

class TrieNode {
  char data;
  TrieNode children[26];
}

public class Trie {
  private TrieNode root = new TrieNode('/'); // 存储无意义字符

  // 往Trie树中插入一个字符串
  public void insert(char[] text) {
    TrieNode p = root;
    for (int i = 0; i < text.length; ++i) {
      int index = text[i] - 'a';
      if (p.children[index] == null) {
        TrieNode newNode = new TrieNode(text[i]);
        p.children[index] = newNode;
      }
      p = p.children[index];
    }
    p.isEndingChar = true;
  }

  // 在Trie树中查找一个字符串
  public boolean find(char[] pattern) {
    TrieNode p = root;
    for (int i = 0; i < pattern.length; ++i) {
      int index = pattern[i] - 'a';
      if (p.children[index] == null) {
        return false; // 不存在pattern
      }
      p = p.children[index];
    }
    if (p.isEndingChar == false) return false; // 不能完全匹配，只是前缀
    else return true; // 找到pattern
  }

  public class TrieNode {
    public char data;
    public TrieNode[] children = new TrieNode[26];
    public boolean isEndingChar = false;
    public TrieNode(char data) {
      this.data = data;
    }
  }
}

复杂度分析

时间复杂度

构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）

每次查询时，如果要查询的字符串长度是 k，只需要比对大约 k 个节点，就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说，构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。
空间复杂度

用数组来存储一个节点的子节点的指针。如果字符串中包含从 a 到 z 这 26 个字符，那每个节点都要存储一个长度为 26 的数组，并且每个数组元素要存储一个 8 字节指针（或者是 4 字节，这个大小跟 CPU、操作系统、编译器等有关）。而且，即便一个节点只有很少的子节点，远小于 26 个，比如 3、4 个，我们也要维护一个长度为 26 的数组。

在某些情况下，Trie 树不一定会节省存储空间。在重复的前缀并不多的情况下，Trie 树不但不能节省内存，还有可能会浪费更多的内存。

Trie 树与散列表、红黑树

Trie 树对要处理的字符串有极其严苛的要求

第一，字符串中包含的字符集不能太大。即便可以优化，但也要付出牺牲查询、插入效率的代价。
第二，要求字符串的前缀重合比较多，不然空间消耗会变大很多。
第三，如果要用 Trie 树解决问题，那就要自己从零开始实现一个 Trie 树，还要保证没有 bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。
第四，通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

针对在一组字符串中查找字符串的问题，我们在工程中，更倾向于用散列表或者红黑树

本文作者：bobo
本文链接：https://boyolo.github.io/article/23384.html
版权声明：本博客所有文章均采用 BY-NC-SA 许可协议，转载请注明出处！

查看评论