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 <[email protected]>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 <[email protected] > > wrote: > >> the operation is nt extract min ... its *find* min ... >> >> >> >> On Sun, Jul 31, 2011 at 3:02 PM, Abhishek Gupta >> <[email protected]>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 < >>> [email protected]> 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 <[email protected]>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 <[email protected]>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 [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. >>>>>> >>>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> -- >>>> 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. >>>> >>> >>> >>> >>> -- >>> 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 [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. >>> >> >> -- >> 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. >> > > > > -- > 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 [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. > -- 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.
