heap - Do I have to make the possibilities of position of 4th minimum?

Question

A Min heap was constructed and the place of second minimum is at the right child of the root. You are asked to mark all possible places of the fourth minimum, assuming that duplicates don’t exists in the data structure.

标签： heap

Answer 1

如果最小堆中没有重复，则每个节点的父节点都小于子节点。

每个节点可以有任何值，但不能与另一个相同。为了使图表更容易，只需使用整数。

            [1]
    [A]             [2]
[B]     [C]     [D]     [E]

• D 和 E 未排序。
• D 大于 2。
• E 大于 2。
• A 大于 1 但不大于 2。

因此，A、B、C、D 或 E 中的任何一个都可能是 4。