Do we have a priority queue that supports a delete operation with the same complexity as other operations?
The priority queue is known for extracting a max or min element from a set. Two common operations in the priority queue are Insert and DeleteMin / DeleteMax . Do we have a priority queue that supports Delete (x) ? The Remove (x) value is two to remove element x from the priority queue .
A naive way to do this is to find element x and remove it, but this will take linear time. I am looking for a better algorithm.
source to share
Several types of priority queues support this operation. Typically, this can be done if the delete operation (x) takes x as a pointer within the data structure indicating which element to delete. For example, in a binomial or Fibonacci heap, where each element is stored as a node in the forest, an insert (x) operation can send a pointer to the node that contains the element x and delete (x) can then follow the pointer to quickly find the element to delete.
In most priority queues that support delete (x) in this way (Fibonacci heap, binomial heap, spike heap, etc.), the complexity of delete (x) is the same as that of delete-min , but it depends on the specific implementation of the structure data.
Hope this helps!
source to share
There is a cheat way that I use if the Priority Queue library does not support features Delete(x)
.
I will use 2 priority queues, ORI
and DELETED
.
ORI
will be my original priority queue, and DELETED
will be a pool to mark which items have been removed.
To add an element, just add it to ORI
. To remove an item, just add it to DELETED
.
The magic happens when you request the top (like Min / Max) of the priority queue:
1) While the top ORI
is equal DELETED
, remove the top of both priority queues (using DeleteMin / DeleteMax)
2) When the top of both priority queues is not equal, the top ORI
will be the actual "top" you are looking for.
This delays the "deletion" somewhat while the item to be deleted is at the top of the priority queue. This works because if an item is marked deleted, is not the top of the priority queue, the top of the priority queue will not change.
However, the disadvantages of this "cheat" are that more memory is required to store items marked as "delete".
The complexity for the delete function ends up being made as an arrow O (log N)
Edit: This way you don't have to implement your own data structures: P I have used this technique in a C ++ programming competition using STL priority queues.
source to share