So you need a task scheduler with expiration and priority on each task. Interesting Problem..
as peter said about marking the task in heapB to be deleted. but this needs searching everytime you pop off an old item [complexity: O(len(heapB))]. you may as well use python del on it as complexity is same. But if you already know the where to look in the heapB then you can avoid searching and thereby reducing the complexity. you can do this by saving the references of heapB in heapA and viceversa and if you marking delete on a number of low priority tasks, then it can increase your heapB enormously because being low priority items they can stagnate. to resolve this error you have to perform linear checking iterations at every critical length (this critical length can be obtained mathmatically), so that your amortized complexity of push, pop remains log(number_of_valid_tasks_at_any_time); the number of valid tasks at any time are those tasks which are not expired at the time. My Algorithm: version_a: https://gist.github.com/9ce7a0e534c6e768239e this version has simple scheduler which has methods for popping high priority one and popping oldest task. But this version has a disadvantage, i.e If lets say you are pushed some 10**5 tasks with priority 2, and then pushed some 10**5 tasks with priority 1. and then you decided to pop the oldest 10**5 items. in this version that 10**5 elements will stagnate in priority heap if in future all priorities are less than 1. now this is not a big issue but if you are running a webserver and over a span of 5 days there could be 10**10 tasks, and even if half of those tasks stagnate your server is going to crash with out of memory. version_b: https://gist.github.com/99b4d590753ba234eeed this version resolved that stagnation. this one will run sweeps whenever there are more than half of useless items, thereby giving us an amortized complexity of O(log(n)) for push, pop, etc but this version doesn't have the feature of expiration. version_c: https://gist.github.com/9dfd0d291672c0ffa5c3 in this one we simply keep a variable expiration, and relieve the expired tasks on any operation. i have coded it in such a way that expiration is specific time, you can change it to delta time if you want to. Time Complexity: O(log(n)) insertion, O(log(n)) deletion [amortized] Space Complexity: O(n) [amortized] here n is number of valid items i.e which are not expired. I hope this helps with your problem PS: sorry for posting links, it's just that the code is large for email. I'm using minimum number has highest priority convention. On Fri, Jan 8, 2016 at 10:15 PM, Sven R. Kunze <srku...@mail.de> wrote: > Thanks for your suggestion. > > On 08.01.2016 14:21, srinivas devaki wrote: >> >> You can create a single heap with primary key as timestamp and >> secondary key as priority, i.e by creating a tuple >> insert the elements into the heap as >> (timestamp, priority) > > I think I cannot use that because I need the list sorted by both criteria. >> >> If there is any underlying meaning for creating 2 heaps. please mention. > > > I use two heaps because I need to insert arbitrary items fast and remove the > ones fast which are too old (timestamp) or are next in order (priority). > > Basically a task scheduler where tasks can be thrown away once they are too > long in the queue. > > >> On Fri, Jan 8, 2016 at 4:22 AM, Sven R. Kunze <srku...@mail.de> wrote: >>> >>> Hi everybody, >>> >>> suppose, I need items sorted by two criteria (say timestamp and >>> priority). >>> For that purpose, I use two heaps (heapq module): >>> >>> heapA # items sorted by timestamp >>> heapB # items sorted by priority >>> >>> Now my actual problem. When popping an item of heapA (that's the oldest >>> item), I need to remove the very same item from heapB, regardlessly where >>> it >>> is in heapB. And vice versa. >>> >>> Is there a datastructure or a simple trick to achieve that in an >>> efficient >>> matter? >>> >>> Best, >>> Sven >>> -- >>> https://mail.python.org/mailman/listinfo/python-list > > -- https://mail.python.org/mailman/listinfo/python-list
