@sagar : deletion in logn, check http://en.wikipedia.org/wiki/Heap_%28data_structure%29 i would say that the "re-heapify" is implicit just as the "re-balance" is implicit in balanced bst
On Mon, Aug 22, 2011 at 12:58 AM, sagar pareek <sagarpar...@gmail.com>wrote: > +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 <duman...@gmail.com> 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 <love.for.programm...@gmail.com> >> 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
