""" # first we need to add it to stack and make sure we keep track of freq frequency = defaultdict ( int ) def push (self, x ) : """
Can you spot them?):Ĭlass FreqStack ( object ) : def _init_ (self ) :
#Python priority queue with tuples crack
Here’s a first crack (note, this implementation has a few issues.
To pop items, we will remove the lowest priority item, grab the element (3rd element of each tuple), reinsert the item with a decremented frequency (frequency-1, insertion_order, element), and return element. This is the opposite of what we need, but we can accomplish this by negating the frequency as well as the insertion_order (actually, I will accomplish this by setting the insertion_order to sys.maxint and decrement the counter with each insertion).
One thing to also note is heapq’s pop() method returns the item with the lowest priority. insertion_order will be a counter that will be incremented with every insertion. So we will be pushing tuple of the form (frequency, insertion_order, element). Since the insertion order will always be unique, we’ll be safe to use the last element of each tuple to store the integer itself. We always want to return the element with highest frequency, so the first element will be the actual frequency. This may be a bit of a leap here, but if we use a monotonic insertion counter, will be able to mimic the behavior of a stack as far as keeping track of insertion order goes. Side question - how does the heapq deal with ties? Let’s see:Īs expected, ties will be broken by the second element in the tupleīut the question really is, what should we put in the second element? We will also keep up to date a frequency dict and append the item to a stack. So, how about we try popping/pushing out of the queue to keep track of the occurrences? My thinking is as follows - when calling push(), we will reinstantiate a heapq, and reinsert all of the items from the stack into the queue. It will also allow us to choose the comparison method in the case of ties. It will allow us to keep track of more information, which will be needed as we need the integer with maximum occurrence (and not just the most frequent occurrence). It is possible to push tuples into the heap, which will give us more flexibility. For our problem, we need to think a bit more closely on what we are actually going to enqueue. In this way, you push a bunch of values into the heap and be guaranteed to receive the values back in ascending order. Pushing integers will invoke the default comparison method - since 5 is smaller than 6, 5 will be returned. heappush (heap, 6 ) # access the min value without removing One thing to note is heapq’s pop() method returns the item with the lowest priority. This library provides a heap queue, which implements a min heap. I’m using Python 2, so the go to library would be heapq. Okay, so a priority queue could be helpful to us. How about a priority queue? A priority queue will be able to give us the history that we need if we can somehow store in it each element’s frequency of occurrence. But this still doesn’t give us the MOST frequently occurring value, and more importantly doesn’t store the history of most frequently occurring value, as we will need this to be able to call pop() in succession and return the correct value.
I can think of data structures that can accomplish one of those tasks each - a vanilla list for the insertion order, and a frequency hash ( dict) for the frequency. However, it’s not clear to me initially what to use. It would be helpful to have a structure that captures both the frequency as well as the insertion order. Okay, at first glance this looks like a problem where I will need to use a few different data structures Class FreqStack ( object ) : def _init_ (self ) : pass def push (self, x ) : pass Initial Thoughts and Approach
0 kommentar(er)
