Search code examples
arraysdata-structuresheapsort

An array that is a max heap, but whose reverse is not a min heap?

I have a question that I believe I understand, but am looking for some verification. I know that in order to be a min heap, the child must be greater than the parent, and in order to be a max heap, the parent must be greater than the child. If so, is this a valid answer to the following question:

Create an array with 5 elements, that is a max heap, but whose reverse is not a min heap.

A = [ 100, 50, 49, 40, 41 ]

    100
  |     |
  50     49
 |  |
40  41

So, just verifying, that if I read this tree as a min heap, I'd read 40, 41, 50, 49, 100? Thank you - this confuses me and any insight into Heaps would be awesome!

Solution

  • Simple counterexample:
    Consider A = [10 7 3 6 5] - array is valid max-heap. 

         10
   |     |
  7      3
 |  |
 6  5

    But reverse B = [5 6 3 7 10] is not min-heap

    So not all reverses of max-heap arrays are mean-heaps