0

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?

Improve this question
2
  • Sounds like some homework :p, what have you tried first? Commented Nov 12, 2013 at 3:19
  • I already tried first...and not a homework. I just heard that it can that's why i posted :) Commented Nov 12, 2013 at 3:24

1 Answer 1

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

I made a MimHeap and MaxHeap
My goal is making a Min-Max Heap so in MinMaxHeap when i implement deleteMax() i coudnt find the way deleting max value at each heap at the same time.
@user2981593: A Min-Max Heap is not a data structure that contains two separate heaps. It is a single heap that is structured in a particular way. The original paper: Min-Max Heaps and Generalized Priority Queues.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.