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.
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.