CODEWITHSUNDEEP
algorithmdata-structuresheap
ThunderWiring
ThunderWiring

Reputation: 738

same key multiple times in a heap

In a heap (whether max heap or min heap), is it possible that there can be the same key twice or more than once?

How can this scenario corrupt the time complexity of O(n) for makeheap() and O(log(n)) for insertion and removing?

example: is the following heap valid?

 1

/  \

1   1

Upvotes: 0

Views: 1718

Answers (2)

shx2
shx2

Reputation: 64318

is it possible that there can be the same key twice or more than once?

Yes, it is possible.

How can this scenario corrupt the time complexity?

It cannot. Take a look at a heap implementaion of your choice. It would be simple and straightforward to prove an upper bound for complexity in order to derive the O-notation, without making any assumptions about the values involved. This means that, for example, values can repeat, without affecting complexity.

Upvotes: 1

user2566092
user2566092

Reputation: 4661

Sometimes theoretical perturbation arguments are good to answer this kind of question. Imagine for every element in the heap, you also store an "index" of the number of operations you have done so far either building or accessing or whatever into the heap, at the time the element is inserted into heap. Thus every element in the heap has a secondary unique id that you can use to break "ties" when two values in the heap are equal and you still need to compare them. Then clearly the heap will run as usual, with the same running time guarantees. Figuring out such perturbations is the easy way around these kinds of degeneracy problems, especially in computational geometry problems when you don't want 3 points on a line, or 4 points on a circle, etc.

However, I gave you a somewhat pedantic answer to your question. I believe the real truth is, in a heap operation, you can make arbitrary decisions as to which element to swap with a parent when there are ties, as long as the swapped child is less than or equal to its parent (assuming a min-heap), and everything should work fine. The only thing that could make things more complicated is if, for some reason, you wanted to pop all ties for min-value off the heap at once. But even this is not really a big deal, I believe.

Upvotes: 0

Related Questions