1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

implementation of priority queues

Discussion in 'Engineering Concepts' started by siya, Oct 15, 2008.

  1. siya

    siya New Member

    Joined:
    Oct 15, 2008
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,285
    Likes Received:
    364
    Trophy Points:
    83
    Searching the forum would give you nice code for the same.
     
  3. oogabooga

    oogabooga New Member

    Joined:
    Jan 9, 2008
    Messages:
    115
    Likes Received:
    11
    Trophy Points:
    0
    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.
     

Share This Page