Go4Expert

Go4Expert (http://www.go4expert.com/)
-   Engineering Concepts (http://www.go4expert.com/forums/engineering-concepts/)
-   -   implementation of priority queues (http://www.go4expert.com/forums/implementation-priority-queues-t14549/)

siya 15Oct2008 07:48

implementation of priority queues
 
hi,
I am siya.....i have a query regarding priority queues.......how can priority queues be implemented such that the operations of priority queue,that is Insert and ExtractMax be done in constant time....Using priority queues with heaps takes log n time to implement these opearitons........what data structure helps to implement these in O(1) time....

Thanks in advance....
siya.

shabbir 15Oct2008 10:08

Re: implementation of priority queues
 
Searching the forum would give you nice code for the same.

oogabooga 16Oct2008 01:26

Re: implementation of priority queues
 
I don't see how both Insert and ExtractMax can be O(1). Obviously Insert can be O(1) if you just append new elements to the end of a vector, but then ExtractMax would be O(n) since you'd have to search the entire vector. You may be able to take advantage of special properties of your key, but in general you won't be able to get both operations below sqrt(log n) or maybe log log n.


All times are GMT +5.5. The time now is 07:41.