Is this a valid MaxHeap structure?

Question

I am trying to convert a minHeap class to a maxHeap class. I was given the code for the minHeap class, one method of which was add. It looks like this:

while (index > 1 && getParent(index).compareTo(newElement) > 0)

The first node is automatically set to null, so everything that gets add is placed in node 1 onwards. This code as already stated gives a minHeap structure. So change it to maxHeap, I simply flipped the comparator sign like so:

while (index > 1 && getParent(index).compareTo(newElement) < 0)

The items I am entering are being stored by an integer value. In order of insertion they are:

3
7
8
10
6
1
9
2

In the minHeap structure, these are stored in nodes like so:

            1
       2         3
    6     7   8     9
 10

In the maxHeap structure, changing the sign stores them like so:

           10
      8           9
   2     7     3     6
 1

Note how they are no longer in the same kind of sequential order as they were in the minHeap structure. Does this matter or is it still a valid maxHeap?

Apologies for my awful attempt at showing a tree like structure.

Answer 1

Yes. If your heap is being stored as you say it is a valid Max-Heap. A Max-Heap have the property that every node (except the root) contain a value that is less than or equal to its parent. Your heap obey this rule.