i need to design a data structure that supports the following operations: Group S which has n numbers:

1. Init(A,n) - init ds given n elements = O(n)
2. insert(x) - insert element x = O(logn)
3. find_min() - return minimum element without taking it out from the structure = O(1)
4. find_max() - return maximum element without taking it out from the structure = O(1)
5. extract_min() - delete minimum element = O(logn)
6. extract_max() - delete maximum element = O(logn)

Any ideas or suggestions on how to approach this problem or how should it be implemented would be kindly appreciated

CodePudding user response：

That would be a Min-max heap. Here is a nice article about it by Malte Skarupke with a C implementation. Here is a Java implementation.

CodePudding user response：

This is a heap data structure. More specifically a binary heap.

There are 2 types of heaps basically, a min heap in which minimum value element is present at the root node and a max heap in which maximum value element is present at the root.

So, according to the constraints given, the data structure might be composite, consisting of both min heap and a max heap. Since you need both min and max in O(1) time complexity, you will have to keep both heaps.

Also, init process that takes O(n) time complexity, this process is called heapify, or building heap from an existing array