java - Understand how min-max heap looks like after after delete-min and delete-max

Question

I have a specific question about min-max heap related problem in Java.

If you have inputs in this order:

71, 8, 41, 100, 60

Would the tree look like the following?

                   8
           100           41
       70       60

What about after deleteMin and deleteMax?

I am trying to understand what would happen if the max node is somehow smaller than some of the min nodes... If you can help me by explaining it with a tree that would be great :)

Answer 1

创建此输入的最小堆的过程是这样的：

        71
      8    41
  100  60

然后它看起来像这样：

     8
  71  41
100 60

最后，它看起来像这样：

      8
  60    41
100  71

此时，每一个非叶子节点，其值都大于其子节点的值。所以，在你删除最小值之后，上面的最小堆的根会被删除，结果是这样的：

     41
  60    100
71

如果你删除最大值，那将是最后一个被删除的元素。那么结果将是这样的：

     8
  60    41
71

我希望这能帮助你理解堆。