Efficient data structure for extractMin and extractMax

Hello Everybody,

I need to design or use an existing data structure which performs extractMin, extractMax and insert efficiently. What I mean by extractMin (resp. extractMax) is to retrieve the minimum (resp. maximum) element in the data structure. I know that if I use a red-black tree or avl tree or any other balanced binary tree, each of three operations will be O(logn). I am looking for something more efficient.

Any idea?


Best,
-hkullana

Quote:

---

Originally Posted by hkullana

I need to design or use an existing data structure which performs extractMin, extractMax and insert efficiently. What I mean by extractMin (resp. extractMax) is to retrieve the minimum (resp. maximum) element in the data structure. I know that if I use a red-black tree or avl tree or any other balanced binary tree, each of three operations will be O(logn). I am looking for something more efficient.

---

You can get constant time extractMin and extractMax at the cost of a slightly more expensive insert with a balanced binary tree simply by keeping track of those elements.

If your stated requirements are really all there is to it, then you can get constant time extractMin, extractMax and insert: use a singly linked list that keeps track of its tail, and also keep track of the minimum and maximum.

Using a heap tree structure, you can extract the min in constant time (min heap)
same for max

Quote:

---

Originally Posted by mellice

Using a heap tree structure, you can extract the min in constant time (min heap)
same for max

---

Yeah, but not both, unless you use two heaps that consist of the same elements. Of course, the advantage is that if the elements are removed, you can still efficiently do extractMin and extractMax, but then hkullana did not mention anything about removing elements.

Thank you for the answers.

I think I should clarify that what I mean by extractMin is to retrieve and *delete* the minimum element (same for extractMax). Is there still a way for doing these operations in constant time while insert stays at logarithmic time?

Quote:

---

Originally Posted by hkullana

I think I should clarify that what I mean by extractMin is to retrieve and *delete* the minimum element (same for extractMax). Is there still a way for doing these operations in constant time while insert stays at logarithmic time?

---

It occured to me that using two heaps won't work: if you extractMin from the min-heap, removing the corresponding minimum from the max-heap is not going to take constant time in general.

Quote:

---

Originally Posted by hkullana

I think I should clarify that what I mean by extractMin is to retrieve and *delete* the minimum element (same for extractMax). Is there still a way for doing these operations in constant time while insert stays at logarithmic time?

---

I don't think this can be done. If you use a balance binary tree (i.e. AVL), you could keep track of the minimal and maximal elements with pointers, but on deletion you will have to re-balance the binary tree which costs O(log n). I'm not sure if you can beat this using a different type of balance tree (Red-Black?)

Realistically you might just be better off just using an off-the-shelf balance binary tree library and eating the O(log n) cost of deleting the maximal element. Unless N is REALLY huge or you call it a TON, it would be surprising to find that it was the limiting factor of your program.

Wikipedia claims Fusion trees achieve O(1) on minimum (just see it, not remove) and O(sqrt(log n)) on insert and extractMin. See: http://en.wikipedia.org/wiki/Priority_queue

Some lectures notes I found on the topic: http://courses.csail.mit.edu/6.897/s...4/lecture4.pdf