Switch from minimum heap to maximum heap without reordering the internal matrix

Question

Suppose we have a bunch of minutes with some elements that satisfy the heap property. What happens if I change the algorithm from the minimum heap to the maximum heap without rearranging the internal array?

That is, if I leave the array unchanged, what happens when I add an element to the internal array?

Answer 1

Consider the following example from Wikipedia :

The array view will look like this:

[1, 2, 3, 17, 19, 36, 7, 25, 100] 

Now we "change" the heap from min to max, but without rearranging the elements and insert a new element "25". The position of the array will be 9, so the parent of the node is "19" at position 4.

After insertion, we must re-compare the new element with our parent in order to provide the heap property (now max-heap => the parent should be larger than the child). Thus, we must change “25” to “19”, “2” and “1” until it becomes the root of the node.

Now the max-heap property is executed for the root of the node (its children are really smaller), but not for other nodes, for example. "3" is still the parent of "7" and violates the maximum heap condition.

In conclusion: Doing what you describe does not change the minimum heap to the maximum heap.

Answer 2

You just hit a bunch.

You need to reassemble (this can be done in O (N) time).