Question

1. 堆 heap

堆的本质是一种数组对象，数组下标从 1 开始

堆可以被视作一棵完全二叉树，二叉树的层次遍历结果与数组元素的顺序对应，树根为 A[1]。

对于数组中第 i 个元素，其对应在二叉树中的父母孩子结点位置的计算如下：

PARENT(i)
  return i/2
LEFT(i)
  return 2i
RIGHT(i)
  return 2i+1

2. 最大/小堆(max-heap/min-heap)

从二叉树的角度看，对于所有非 root 结点，满足 node->parent ≥ node / node->parent ≤ node

从数组的角度看，对于所有下标大于 1 的元素，其下标为 i，则满足 A[PARENT( i)] ≥ A[i] / A[PARENT( i)] ≤ A[i]

3. 高度 height

结点的高度：从结点到叶子所经过的边的数量，叶子结点的高度为 0

二叉树的高度：树中高度最高的结点的高度，只有一个结点的树高度为 0

堆的高度：把堆看所作二叉树时的高度