Give an efficient data structure supporting the following op

Give an efficient data structure supporting the following operations.

• Insert(S, x): add x to S.

• Delete M ax(S): Delete the maximum value from S.

• Delete 100 M ax(S): Delete from S the 100 largest element.

• Delete 100 M in(S): Delete from S the 100 smallest element.

Solution

For this work you have to use Max-Min Heap Data Strucutre to perfrom these operations. becuase insert will not take any problem. Problem is deleting 100 max and 100 min element in the data.

Suppose we have to delete 100th maximum element from S. So we hyave to find the element and then remove it .

Simple brute force algorithm says that find 1 to n maximum element one by one and then remove it.

But there is one more suitable solution that he can help you easily.

Algo:

1. First take three input S[]:total stored data, n: total number of element, max_e: maximum position we hae to delete.

2. First we have to create a max heap of (n-k) element.

3. after this, you will get an heap of k element and root is the maximum element.

4. Now you have to apply a loop for all remaing element k.

5. And compare with the root.

6. If(root > current element in remaining elements)

      then replace it and again run max_heap procedure to find new max heap.

7. else ignore it.

8. After this loop the root element of max heap is your 100th largets element if k is 100.

Same you can do with min heap.

Now you can easily delete any max or min element from the data.