Well, I thought of running two queues, one a priority queue, the other a normal queue, but that still doesn't get you there. Hmm... I'm stumped. Anyone else get this one?
If the value space is little you can use an array of queues for each possible value, to the priority problem (get_min). And link every entry in FIFO order too, to push_rear() and pop_front() in O(1).
Or an hashtable where the key is the value on which apply the sort and the value a list of all entry with the same value. Then the structure has to mantains also the FIFO order linking the entries with a linked list.
Not sure that works, Dashie. The value space would have to be very small to do the former solution. And how does the hashtable solution deal with deletes? The problem is that you potentially need to do a linear scan of the queue to find the minimum again in some situations, don't you?
Okay, what's the answer to this one? Implement as a heap and you can't do all three simultaneously. What's the answer?
ReplyDeleteduplicate items in the queue!
ReplyDeleteWell, I thought of running two queues, one a priority queue, the other a normal queue, but that still doesn't get you there. Hmm... I'm stumped. Anyone else get this one?
ReplyDeleteBut pop_front has to return elements in FIFO order relative to push_rear or the same element of get_min?
ReplyDeleteHow many different values can you have in the queue?
ReplyDeleteIf the value space is little you can use an array of queues for each possible value, to the priority problem (get_min). And link every entry in FIFO order too, to push_rear() and pop_front() in O(1).
ReplyDeleteOr an hashtable where the key is the value on which apply the sort and the value a list of all entry with the same value.
ReplyDeleteThen the structure has to mantains also the FIFO order linking the entries with a linked list.
Not sure that works, Dashie. The value space would have to be very small to do the former solution. And how does the hashtable solution deal with deletes? The problem is that you potentially need to do a linear scan of the queue to find the minimum again in some situations, don't you?
ReplyDelete