kruptof

Lect, I read through your pseudo code, it took a while for the penny to drop, but when it dropped it dropped good, as I saw that in proposal I was manipulating items that have not been de-queued (the whole subtraction thing), while with yours it was just comparing two times.

I got I more questions about this, what happens if I would like to remove an item from the queue, which is not at the head of the queue(It’s a requirement that an item can be deleted at any time, though i don't think it's a event that will frequently occur).
I had two proposals, loop through each item (I know O(n)) and when you find the item delete it and re-heap from that point on. Or change the data structure to a balanced tree which enforces total order in which the above operation should be much faster. Or keep a list of deleted items and when an item is de-queued check if it’s in the deleted list.

__________________

lectricpharaoh

This is good. I wasn't sure if my explanation was clear, but it seems you now know what I was getting at.
Hmm. This is an additional requirement, and while it does complicate things, it's not a big change. One thing you can do is track which events have been 'deleted' without actually deleting them. Then, when the timer fires, you can check if the event is marked as deleted, and if so, ignore it. You need some mechanism to determine if an element (the event) is a member of a set (the list of deleted events). Using a Bloom filter comes to mind, but this may not be acceptable for your purposes as there is a low but nonzero probability of false positives (creating the potential to miss events).
Yeah, you could traverse the heap and delete the node holding the event; there's no need for an explicit re-heap operation, as this is iimplicit with a change to the heap. Another thing you could do is traverse the heap until you find the node you want to delete, and flag it as deleted (this will require a flag in your node structure/class).

Perhaps the best solution is to have your heap hold references to items, rather than the items themselves. Presumably, to delete event X, you require some means of identifying event X. In other words, say you have a deleteEvent() method- what will you pass to it? Thus, if you can specify an event to delete, you already have a reference to the event, and can adjust its properties to deactivate it (setting Handled to true, if it's the .NET Event class or a derivative, or doing something similar for your own class). If you are using a structure, rather than a class, it will be a value type, so you will need to muck with pointers directly (generally not the best practice in C#). If you're using a class for your event type, it will be a reference type, so no problem.

Perhaps you could give me some more details on what you're trying to do. When you say 'event', do you mean the Event class from the .NET framework, one derived from this, or a totally unrelated class used to represent logical events? How critical is it that events are handled? Mouse movement events, for example, aren't too critical- if the system drops (ignores) one of every few hundred movement events, the user probably won't even notice. Key press/release events for the keyboard keys or mouse buttons, on the other hand, are critical; missing these events will cause obvious problems. Likewise, what will be the result of handling an event that has been cancelled? Will it simply waste a bit of CPU time, or will it mean the event gets handled multiple times (say, by different handlers, with one earlier in the chain cancelling the event to prevent later handling)? If the latter, what are the consequences? If the former, it's probably acceptable to ignore cancellations, especially if the event code executes quickly.

__________________
And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot.
- Vaarsuvius, Order of the Stick

kruptof

I am using a structure to hold the represent queue items, and i am using a class to represent the Min-Heap.

I was thinking one way to eliminate the O(n) of the deletion operation is to put all queue items in hash table, let the queue item structure hold a key (duetime) and the hash value of the item, so when i want to delete an item i would get the hash of the item, and change it's status to deleted, hopefully with no collisions this should take O(1) best case right?

When the program is run, at loading it gets a collection of urls of rss feeds and loads their ttl (according the rss 2.0 spec "It's a number of minutes that indicates how long a channel can be cached before refreshing from the source") and when that time has passed it must check if there any new posts.

Sorry I think I used the term event incorrectly, I think it's better described as an update or refresh task.

I would say for something like this is of a critical level 3-4 (5 being the max), because if the ttl is pretty big, then you don't want to miss an update, and update a day late or something.

Well if the task has been cancelled (such as if the feed entry is deleted) and it's fired be it by an accident or on purpose it will check if the entry exists in a data table which contains all the available urls (if a feed is deleted it will be deleted from here as well) and if it does exist, it goes and trys update from that url, if it doesn't exist the function just returns.

__________________