CODEWITHSUNDEEP
algorithmdata-structures
JudeLee
JudeLee

Reputation: 13

How to implement deleteMax() in MinHeap taking log(n) time

I'm implementing MinHeap I know how to implement deleteMax() but it takes O(n) time But I need O(log(n)) algorithm..

I searched and didn't find a way to do this, if it exists Is there any way that I can deleteMax() in O(log(n)) times?

Upvotes: 0

Views: 126

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 134125

You could create a Min-max heap, which does deleteMin() and deleteMax() in O(log n) time.

That's the only O(log n) way I know of to do what you want. The Min-max heap has the same asymptotic bounds as a Min-heap or Max-heap, but its real world running time will be somewhat longer.

Upvotes: 4

Related Questions