here is what i think should be done to do thees operations in O(1)....it is quite popular interview question..
i am using two stacks one stack arr[] in which elements in the elements will be pushed as they are normally done in a stack maintain another stack min[]....whenever you insert an element in original stack,insert the index of min element up to that point. so at any point you want to take the min element ,go to the min stack,get the index,value and fetch the element. one example would be -- arr[] min [] 45 2 78 2 38 2 67 0 50 0 hope it is clear now... !! -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Sun, Jul 31, 2011 at 3:30 PM, Shubham Maheshwari <shubham....@gmail.com>wrote: > i am givin solution for implementing a queue or a stack ... > in which ...inserting, delelting and finding min element is of O(1). > > hope this is clear now ... > > On Sun, Jul 31, 2011 at 3:19 PM, Abhishek Gupta > <gupta.abh...@gmail.com>wrote: > >> Qn is : Create a data structure where inserting, deleting and finding the >> >> minimum element all have O(1) time. >> >> so after deleting the minimum element, where will you point min pointer? >> >> Sorry if i m wrong >> >> >> On Sun, Jul 31, 2011 at 3:11 PM, Shubham Maheshwari < >> shubham....@gmail.com> wrote: >> >>> the operation is nt extract min ... its *find* min ... >>> >>> >>> >>> On Sun, Jul 31, 2011 at 3:02 PM, Abhishek Gupta >>> <gupta.abh...@gmail.com>wrote: >>> >>>> @shubham maheshawari >>>> >>>> deletion can't be performed in O(1). >>>> after extracting the min element, we need to find the next minimum >>>> element, and worst case will take O(n) time. >>>> >>>> On Sun, Jul 31, 2011 at 3:00 PM, Shubham Maheshwari < >>>> shubham....@gmail.com> wrote: >>>> >>>>> hw cn u ensure that the elements are inserted in sorted order ... >>>>> wat if the elements are coming randmly ... >>>>> >>>>> On Sun, Jul 31, 2011 at 2:49 PM, muthu raj <muthura...@gmail.com>wrote: >>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> Use a circular linked list with elements being inserted in sorted >>>>>> order. >>>>>> >>>>>> Inserting minimum element : >>>>>> >>>>>> struct node *p; >>>>>> p is a pointer to last node in the circular singly linked list. >>>>>> newmin->next=p->next; >>>>>> p->next=newmin; >>>>>> >>>>>> >>>>>> Deleting minimum element: >>>>>> >>>>>> struct node *temp; >>>>>> temp=p->next; >>>>>> p->next=p->next->next; >>>>>> free(temp); >>>>>> >>>>>> >>>>>> Retrieving minimum element : >>>>>> >>>>>> return (p->next->ele); >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> *Muthuraj R >>>>>> IV th Year , ISE >>>>>> PESIT , Bangalore* >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> On Sun, Jul 31, 2011 at 2:08 AM, naveen ms <naveenms...@gmail.com>wrote: >>>>>> >>>>>>> @shubham...i have a doubt.can't the same be done with singly linked >>>>>>> list?? >>>>>>> >>>>>>> -- >>>>>>> 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. >>>>>> >>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> Abhishek Gupta >>>> MCA >>>> NIT Calicut >>>> Kerela >>>> >>>> -- >>>> 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. >>> >> >> >> >> -- >> Abhishek Gupta >> MCA >> NIT Calicut >> Kerela >> >> -- >> 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. > -- 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.
