+1 Dumanshu This question was asked by amazon :D And answer is BST only coz deletion in heap(min heap) is O(1). And if it is max heap then deletion of min element is O(n).
On Sun, Aug 21, 2011 at 9:13 PM, Dumanshu <[email protected]> wrote: > We can't use a heap. Balanced BST is correct because "Deletion of the > smallest element Insertion of an > element if it is not already present in the set" -> for this we need > to search for the element and searching in heap is O(n). > > On Aug 21, 6:16 pm, priya ramesh <[email protected]> > wrote: > > A data structure is required for storing a set of integers such that each > of > > the following operations can be done in (log n) time, where n is the > number > > of elements in the set. Deletion of the smallest element Insertion of an > > element if it is not already present in the set Which of the following > data > > structures can be used for this purpose? > > > > ยท Pick one of the choices > > > > A heap can be used but not a balanced binary search tree > > > > A balanced binary search tree can be used but not a heap > > > > Both balanced binary search tree and heap can be used > > > > Neither balanced binary search tree nor heap can be used > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
