堆

堆是一种满足特定条件的完全二叉树 (而非满二叉树).

因为其为完全二叉树, 所以可以通过数组来高效地储存.

• 左子节点索引为: \(2i + 1\).
• 右子节点索引为: \(2i + 2\).
• 父节点索引为: \(\frac{i - 1}{2}\).

可以分为两种:

• 最大堆 (max heap).
• 最小堆 (min heap).

其巧妙之处在于子树也是一个堆.

评论