树，堆和优先队列

depth 和 height：
root 的 depth 为 0，往下第二层 depth 为 1
height：通往叶子的最长的路径上边的条数，叶子的 height 为 0


full binary tree:
除了叶子，其他节点度数都为 2，但是叶子的深度可能不一致

perfect binary tree:
a full binary tree in which all leaves are at the same depth or same level
假设 depth 为 d
则总节点数为 n=1+2+...+2^(d-1) = 2^d-1

complete binary tree:
节点从上到下，从左到右进行填充，得到的 complete binary tree
(有些书上 complete binary tree 定义为 perfect binary tree, 这里不采用)

若节点以从上到下，从左到右进行编号，则 i 的子节点为 2i, 2i+1
i 的父节点为 i/2

n 个节点的 complete binary tree
1. n/2+1,...n 为叶子节点
2. 深度为 floor(lg n)

balanced search tree 是一个大的概念，指能够自动调整，既符合 BST 的要求，又优化树的高度。它有多种实现形式：

• AA tree
• AVL tree
• Red-black tree
• Scapegoat tree
• Splay tree
• Treap

堆：
是一棵 complete binary tree，以下讨论 max-heap
heap property: A[PARENT(i)] ≥ A[i]
若节点以从上到下，从左到右进行编号，heap 对应一个 Array A
这个 array 不是排序的

堆支持以下操作：
MAX-HEAPIFY(A,i)：前提是 i 的左子树和右子树满足 heap property，i 可能违反。
这个操作是目标是以 i 为根的子树满足 heap property。

BUILD-MAX-HEAP(A)
因为 n/2+1~n 都是叶子
因此从 i=n/2 -> 1，MAX-HEAPIFY(A,i)

Heap Sort:
因为 heap 的最大值在 root，也是 A[1]
因此逐渐提取 root，并把 root 和 A 的最后一个节点交换，进行 MAX-HEAPIFY(A,1)

优先队列：
一个 A max-priority queue 支持如下操作：
INSERT(S, x) inserts the element x into the set S. This operation could be written
as S ← S ∪ {x}.
MAXIMUM(S) returns the element of S with the largest key.
EXTRACT-MAX(S) removes and returns the element of S with the largest key.
INCREASE-KEY(S, x, k) increases the value of element x’s key to the new value k,
which is assumed to be at least as large as x’s current key value.