0

So, I was given an "opposite structure" to a "min-max" heap, that is called a "max-min" heap.

  • For every node in even depth, the value of the node is greater or equal to the value of its children.

  • For every node in odd depth, the value of the node is less or equal to the value of its children.

And I was asked to prove that it is possible to find the maximum and minimum value in this very structure that I described, and that I can do so, in constant time complexity.

I tried to read a lot about it, but I don't really get how can I say that the maximum value is particularly the node of this heap, if there might be elements with bigger value in the levels below to root level.

And I did not understand how I would find the minimum value in constant time complexity. Does keeping a track of a "minimum" variable and comparing all the nodes in the odd depth of the tree considered a constant time procedure? Since the tree might not be a "perfect tree"

Very confused about the entire thing. Appreciate if you would help.

Rami Mamadov
  • 11
  • 3

1 Answers1

1

Your definition of the max-min heap is wrong. The max and min property are not only about the direct children, but about all descendants of a node. So we should rephrase your bullet points as follows:

  • For every node in even depth, the value of the node is greater or equal to the value of its descendants.

  • For every node in odd depth, the value of the node is less or equal to the value of its descendants.

From the first rule, it follows that the root (at depth 0) has the greatest value.

From the second rule, it follows that one of the three top nodes has the least value. Since the root has the greatest value, we can know that at least one of the two children of the root has the least value. Which of the two that is can be known with performing just one comparison.

trincot
  • 317,000
  • 35
  • 244
  • 286
  • I appreciate the answer. the root (at depth 0) has the greatest value, since the nodes in even depths follow the "max heap" property? and one of the two children of the root has the least value, because depth 1 is the "highest" odd depth to follow the "min heap" property, so one of the "roots" of the subtrees starting from depth 1 must have the least value according to it? – Rami Mamadov May 24 '23 at 16:15
  • The root node has the greatest value by definition, not "because". Nodes at even depths (so also at depth 0) must by definition have a value that is the greatest in the whole subtree they root. Nodes at odd depths must by definition have a value that is the least in the whole subtree they root. By *consequence* (not *because*), a path from root to leaf where you only look at even indices, forms a non-increasing sequence, and when looking at odd indices you get a non-decreasing sequence. – trincot May 24 '23 at 18:00