Question

Remarks: In all algorithm, always explain how and why they work. If not by a proof, at least by a clear explanation. ALWAYS, analyze the running time complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. Do not write a program. Write pseudo codes or explain in words

Question 5: Five an efficient data structure supporting the following operations. Insert(S, x), Delete−M ax(S), and Delete−1000 th(S) which deletes from H the 100 largest element in the structure. Assume that the number of elements is more than 100. Also assume that the numbers are pairwise distinct and so the 100”th largest element is well defined.

Answer 1

Hello,

Since you have asked for a perfect data structure for insertion, deletion of the max element ( To be precise the 100th largest elements we can look at Certain Data Structures with ex planations;-

1.Linked Lists- If we look at the Linked list, it's insertion time is on average O(1) from beginning and O(n) from the end.But it will not be a perfect data structure as it takes time to have access over the elements while deleting [O(n)].

2. Stack- For pushing and poping the elements it will take time of O(1). But main problem with stack is it's size cannot be changed in the middle if the user is wishing to insert a new element.So not the best Data Structure.

3.Arrays- If we talk about Arrays we can see two types- Unsorted and Sorted arrays. In unsorted arrays we can Do insertion in O(1) but deletion can be costly O(n). In sorted arrays we can see that for Deletion of maximum element we can get Time complexity of O(1), But it is given 100th largest element and given it is pairwise distinct. Hence cannot use arrays.

4. Queues- If we talk about Queues,we can use priority queue data structure which has implementation of Heap.

insertion and deletion can be done in O(log n). As we know that Heap is a Priority based Data Structure which gives importance to Parent first and then to child nodes.

You need to see the working of heaps and priority queues for implementation as it is basic to implement for insertion and deletion. i have explained the right data structure choice and reason,It's implementation is basic. You can read and try for the it.

Thanks.