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
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.11.2024 14:50:02 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
It's not possible. In a heap(or pq) finding an element in itself is linear.
OK! can we implement it on our own such that it work in logarithmic time, is it possible?
Use multiset
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.
Use s.erase(s.find(2)) . It will delete only one 2.
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 .
yes, that's what i am saying. how to delete just one element from multiset.
I think now you know .
Is it possible to delete any random elements from multiset ,suppose multiset contains 10 elements , so is it possible to delete, say 5th element?
This can be possible with the help of ordered set made up in C++.
Order static tree
use multiset instead
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.
Yes