implementation of priority queues

siya's Avatar, Join Date: Oct 2008
Newbie Member
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.
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Searching the forum would give you nice code for the same.
0
oogabooga's Avatar
Ambitious contributor
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.