I am trying to implement min-max heap structure

A min-max heap is a data structure that is identical to a binary heap, but the heap-order property is that for any node, X, at even depth, the element stored at X is smaller than the parent but larger than the grandparent (where this makes sense), and for any node X at odd depth, the element stored at X is larger than the parent but smaller than the grandparent

So far my build and insert heap functions are working fine. My problem is how would I begin to find max value in this heap structure with time complexity O(log n). How would I begin to develop an algorithim for this

As the implementation is in array, find max running time would be O(n) and I have to develop an algorithim with O(log n) time complexity.

parent of a node is at :(i-1)/2

child of a node is at : 2i+1 or 2i+2 i being the index of the node

  • $\begingroup$ Start evaluating "random" examples of depth 2 and 3 using pen&paper. $\endgroup$
    – greybeard
    Oct 5, 2021 at 23:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.