extract-min 运行-time 是多少？为什么？
What is the extract-min run-time and why?
为什么在堆中 extract-min 需要 O(lg n)？
看那里：https://en.wikipedia.org/wiki/Binary_heap#Extract
简而言之，你做三个步骤：
- 首先，用最后一层的最后一个元素替换堆的根。完成时间为 O(1)。
- 其次，将新根与它的 children 进行比较（仍然是 O(1)）。如果一切正常，你就大功告成了！
- 现在很棘手。如果新根比其中一个 children 大（我们认为您在顶部有最小值），请交换它们！现在你（可能）在 child 的子树中遇到了同样的麻烦。继续并在子树中重复步骤 2 和 3！您将 不必 重复此操作的次数多于树中级别的计数，因为每次您都向下一个级别。平衡二叉树中有 O(lg N) 层。注意：如果你的根比两个 children 都大，就用较小的那个交换（你想把它调高）。
为什么在堆中 extract-min 需要 O(lg n)？
看那里：https://en.wikipedia.org/wiki/Binary_heap#Extract
简而言之，你做三个步骤：
- 首先，用最后一层的最后一个元素替换堆的根。完成时间为 O(1)。
- 其次，将新根与它的 children 进行比较（仍然是 O(1)）。如果一切正常，你就大功告成了！
- 现在很棘手。如果新根比其中一个 children 大（我们认为您在顶部有最小值），请交换它们！现在你（可能）在 child 的子树中遇到了同样的麻烦。继续并在子树中重复步骤 2 和 3！您将 不必 重复此操作的次数多于树中级别的计数，因为每次您都向下一个级别。平衡二叉树中有 O(lg N) 层。注意：如果你的根比两个 children 都大，就用较小的那个交换（你想把它调高）。