The frequency is also stored in the heap right? So to do heapify based on frequency, first you have to spot the element on the heap. That itself will take O(n). [ Heapfying after that takes only O(log n) ] If you use a hashmap and store frequencies, and each time mostFrequent is called, do a linear search on the map, it will have the same complexity. Can anyone come up with a better solution?
Karthik R, R&D Engineer, Tejas Networks. On Wed, Sep 7, 2011 at 8:49 AM, *$* <gopi.komand...@gmail.com> wrote: > HI, > Need logic to implement a stack which should support push , pop , top as > well as mostFrequent. mostFrequent should return the most frequently pushed > element. > > I have provided the following logic > have one general stack implementation and one Heap .. (Heapify based on > frequeny not based on element value) > > can any one tell me the time complexity for the above logic .. as well as > any other good algo for the same. > > Thx, > --Gopi > > -- > 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.
