spirited_away_'s blog

How to delete elements in a priority queue ?

By spirited_away_, history, 6 years ago, In English

I want to delete some element in a priority queue not at the top, how should i do? can someone suggest any method, in constant or logarithmic time. How to handle duplicates while removing

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's not possible. In a heap(or pq) finding an element in itself is linear.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    OK! can we implement it on our own such that it work in logarithmic time, is it possible?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Use multiset

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        but suppose we use multiset which consists of s = {3 , 2 , 2 }, now if we want to delete just one 2 from it, its not possible because i think both 2's will be deleted.

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Use set or multiset . Now to get the element on top you can call set_name.rbegin() . To delete some elements just delete it if you know that they are in set . Learn about how to delete an element in mulitset because if you delete an element in multiset by value it will delete all the elements with that value .

      → Reply
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Is it possible to delete any random elements from multiset ,suppose multiset contains 10 elements , so is it possible to delete, say 5th element?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

use multiset instead

→ Reply
»
2 years ago, # |
  Vote: I like it +66 Vote: I do not like it

You can remove the top easily.

If you want to delete another element, you can do it "lazily": when you are given an element to delete from the priority_queue, store somewhere else that this element no longer belongs there (for examplein a map or in a vector of booleans). Then, when you have a "top" request on the priority queue, pop until you reach an element actually still in the queue, according to the other data structure.

→ Reply