I could use a priority queue supporting the
lazy-increase-key operations. The last term is my "invention". It should go like this:
The keys are held somewhere outside of the queue and get increased very often (more often than any other operation). Finding them is not the job of the queue. Ideally, the queue should do nothing when this happens. A later call to
find-min may find out that the priority of the top element has changed and that another element is to be found. In worst case it can mean inspecting all the elements, but to me it looks like it should be fast on the average. Unfortunately, it also looks like I can't explain my idea properly... So let's assume the queue is implemented as a min-heap. When calling
find-min, we find out that the priority of
1 has been increased to
9. The element is misplaced and must be moved somewhere else. The same is true for the
2. When looking at the
3, we see that its priority hasn't changed, and comparing it with the children of
2 tells us, that we've found the minimum.
- 1 -> 9 - 2 -> 8 - 7 - 4 - 3 =3 - 6 -> 10 - 5
The exact algorithm is unclear yet, but it could be a variant of this question.
Some practical figures: Imagine the heap being pretty large (n > 1000), key increasing being more than 10 times as common as
find-and-delete-min. Moreover, bigger elements are more often increased than smaller ones. Given this, trying to restore the heap property upon each increase seems to be very wasteful.
Is there such a structure? Is there such a concurrent structure?