食之无味，弃之可惜。仍不知其所用，但无奈于八股。

树

树，就是一个非空的有限元素集合，其中一个元素为根(root)，余下的元素组合成其 子树。

每个元素称为节点，节点分 根节点 、叶子节点。每个节点的子树数目称为节点的 度。

树中，结点的最大高度为此树的 高度 或者 深度。

    A
   / \
  B   C
 / \  ｜\
D  E  F G

此树中A为根节点，DEFG为叶子节点，A的度为2，C的度为3，叶子节点的度为0。高度为3。

二叉树

每个节点的子树数目不多于2的树，称为二叉树。二叉树的子树分左右。其有以下性质：

1. i层最多有2^i-1个节点；

2. 深度为k的二叉树最多有2^k-1个节点；有2^k-1个节点的树称为满二叉树；由满二叉树从右到左、从下到上地缺少节点，形成的树，称为完全二叉树。

3. 对于任意二叉树，节点数为 n，叶子节点数为 n0，度为2的节点数为 n2，度为1的节点数 n3， 有： n = n0 + n1 + n2， n = n1 + 2n2 + 1， n0 = n2 + 1

4. N个节点的二叉树,最大深度为N，最小深度为 log(N+1)，即完全二叉树。log在此表示以2为底。

5. n个节点的完全二叉树，从上到下、从左到右地进行编号 i = 1...n，有

   • i=1表示根节点；i>1时，此元素的父节点编号为 i/2 的取整；
   • 2i>n时，此元素无左孩子；否则，其左孩子编号为 2i；
   • 2i+1>n时，此元素无右孩子；否则，其右孩子编号为 2i+1；

    A
   / \
   B   C
  / \
  D E    二叉树
 /
F

    A
   / \
   B  C
  / \ ｜\
  D E F G   满二叉树

    A
   / \
   B  C
  / \
  D E     完全二叉树

堆

最大堆／最小堆，两者都是完全二叉树。最大堆是指树中的任意节点大于或等于其孩子节点；最小堆反之。

    14
   / \
  10 12
  / \
  6 5 最大堆

    5
   / \
   6 10
  / \
 14 12 最小堆

初始化

最大堆的初始化。

堆首先是完全二叉树。对于任意的一组数据，按照顺序编号，可以看作是一个完全二叉树，但此树就不一定是堆。如果这组数据是存储于连续的空间，如线性表，那么其中父节点和相应的子节点，可以通过父节点编号＝子节点编号/2(取整)得到节点之间的关系；如果是链表，还要额外地存储左右子节点和父节点的指针，当然将每个链节点的地址另存储为线性表，从而利用父节点编号＝子节点编号/2(取整)公式。

所以，可以利用公式父节点编号＝子节点编号/2(取整)减少程序的访问次数。最大堆需要每个子树的根都大于其左右子节点，那么可以从最后一个子树开始初始化。即，当完全二叉树的节点数为n，那么最后子树的根节点编号应该是 n/2。如此，从 n/2 到 1，不断地构造子树成为最大堆，从而整棵树就成为最大堆。 注意 ，这里的子树不仅仅指三个节点，而是某节点下方的子层，子子层等的所有节点。对于由于节点较小，需要下沉时，需要重新构造以下沉节点为根的子树。总的复杂度为O(nlogn),但实际效果要优于此。

如，

      10
     / \
     6  5
    /\  |\
  14 12 1 2   初始状态
  ／
 8

      14
     / \
    12  5
    /\  |\
   8 10 1 2   结束
  ／
  6

n=8，从8/2=4编号开始。编号4的节点值是14，以此节点为根的子树已经是最大堆了；然后到编号3，节点值是5，这也是最大堆了；编号2，节点值为6，此时需要与左右子节点最大的14进行交换，6下沉，下沉的6改变了以编号4为根的子树结构，所以需要重新构造子树成为堆，6继续下沉；编号1，值为10，小于编号2的14，10下沉，10小于12，下沉右节点。

插入

最大堆的插入操作。插入时，先将新的元素 模拟 放入n+1的位置，再与父节点比较，如果新的元素大于父节点的元素，将父节点元素下移，新元素插入的位置上移。按 n+1 的位置到根节点 这一路径，进行比较，当新的元素大于父节点的元素时，或者到根节点时，比较结束。最后新元素真正插入到相应的位置。由于高度最多是log(n+1)，其操作的时间复杂度为O(logn)

1)
    14
   / \
  10 12
  / \
  6 5

2) x 为新元素的模拟初始位置
    14
    / \
   10 12
   / \ |
   6 5 x

3) 当新元素大于 12 时，
父节点元素12下移，新元素要插入的位置x上移
    14
    / \
   10 x
   / \ |
   6 5 12

4) 当新元素不大于父节点元素14时，
新元素才真正地插入到x的位置上。

删除

堆的删除通常指删除根节点中的元素。最大堆中，n的二叉树删除根节点元素后，节点数目会变为n-1。删除根元素后，根节点为空，模拟将原来的最后一个元素放到此根节点的位置上。然后，与此位置的左右孩子节点比较，取最大元素并将其上移，原来最后的元素模拟下移。如此循环，直到原来最后元素大于此位置上的左右孩子节点元素，真正把原来最后元素放入此位置上。由于高度最多是log(n+1)，其操作的时间复杂度为O(logn)

1)
    14
   / \
   10 12
  / \
  6 5

2) x 为最后一个元素5的模拟初始位置
    x
   / \
  10 12
  /
 6

3) 把 5 与位置x的左右孩子节点中的元素比较，取最大的元素上移，x 位置下移
    12
   / \
   10 x
  / \
  6 5

4) 当原来最后的元素不小于其位置上的任意元素时，将最后的元素真正放入到x位置。

堆的应用

利用堆进行排序，时间复杂度为O(nlogn)。首先，将一组数据初始化为堆，需要的时间为O(nlogn)，然后直接利用堆删除的操作，将根节点提取出来，时间复杂度为O(logn),总的时间为O(nlogn)。这比普通的两个循环的时间复杂度O(n²)要好。