CODEWITHSUNDEEP
algorithmdata-structures
enzom83
enzom83

Reputation: 8320

Switching from min-heap to max-heap without rearrange the internal array

Suppose we have a min heap with some elements which satisfy the heap property. What happens if I change the algorithm from min heap to max heap without rearrange the internal array?

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

Upvotes: 1

Views: 3486

Answers (2)

user1196549
user1196549

Reputation:

You would just screw the heap.

You have to re-heapify (this can be done in time O(N)).

Upvotes: 6

NiklasMM
NiklasMM

Reputation: 2972

Consider the following example from Wikipedia: enter image description here

The array representation of this would 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 array position would be 9 so the parent node is "19" at position 4.

After inserting we must repeatedly compare the new item with its parent to ensure heap property (now max-heap => parent must be greater than child). Thus we must swap "25" with "19", "2" and "1" until it is the root node.

Now the max-heap property holds for the root node (its children are indeed smaller), but not for the other nodes, e.g. "3" is still the parent of "7" and violates the max-heap condition.

To conclude this: Doing what you describe does not change the min-heap to a max-heap.

Upvotes: 8

Related Questions