Give an efficient data structure supporting the following operations. • Insert(S

Question

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. In the algorithm, always explain how and why they work. ALWAYS, analyze the complexity of an algorithm. In all algorithms, always try to get the fastest possible.In all data structures, try to minimize as much as possible the running time of any operation.

In all algorithm, always explain how and why they work. ALWAYS, analyze the 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. In all data structures, try to minimize as much as possible the running time of any operation.

Explanation / Answer

Sorted array strucure which represents linked list is an efficent data strucure
for operations Insert, Delete,Max .....
A simple solution is to maintain a sorted array where smallest element is at first position and largest element is at last. The time complexity of findMin(), findMAx() and deleteMax() is O(1).
But time complexities of deleteMin(), insert() and delete() will be O(n).

As we maintain sorted list.. min and max can be drawn from array starting and extreme edges...
so it is direct, only thing which increases cost becuase of maintaining sorting array always.

************Inserting sample algorithm code ********
void Insert(struct MyDataStructure* myDS, int data)
{
struct LNode* temp = newLNode(data);

// insert the item in List
insertAtHead(myDS->list, temp);

// insert the item in min heap
insertMinHeap(myDS->minHeap, temp);

// insert the item in max heap
insertMaxHeap(myDS->maxHeap, temp);
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.