4
$\begingroup$

I could use a priority queue supporting the find-and-delete-min, and 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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ In general you have zero information preserved between two find-min because the minimum element can now be anywhere (i.e. what if all elements except one increased by a lot?) and you have to scan the whole queue. So worst case will be O(N). Average case under more assumptions, I have to think more. $\endgroup$ – jkff Sep 29 '14 at 17:05
  • $\begingroup$ 1. There certainly appears to be such a data structure -- unless I'm missing something, it looks like you have described it in the question. So is the only remaining question whether it can be made concurrent, without locks? 2. "it looks like it should be fast on the average" - Hmm. I would have guessed differently. Over time, I'd expect the number of mis-placed elements to grow, until most of the items in the heap are mis-placed at any given point in time. Thus find-min might be very slow even in the average case. I haven't thought about it very carefully, though. $\endgroup$ – D.W.♦ Sep 29 '14 at 17:05
  • $\begingroup$ @D.W. 1. I did describe an idea, the exact algorithm is a different story. 2. If a random half of the elements is misplaced, you need to look at 2 of them on the average. When looking at the misplaced elements, I plan to fix them somehow. This should work well amortized as a single fix repairs any number of increases. $\endgroup$ – maaartinus Sep 29 '14 at 18:43
  • $\begingroup$ 1. I'm not clear on what you are looking for, when you mention an exact algorithm. Sounds to me like you already described an exact algorithm. Do you have a specific question about what you think is missing? Can you make the question more precise? 2. You could be right. Asking what fraction of elements will be misplaced in the steady state, on average, would be a good, concrete technical question. I don't know what the answer might be, but it seems like a question that'd be a good fit for this site. (Have you tried simulation, as a way to get some initial intuition?) $\endgroup$ – D.W.♦ Sep 29 '14 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.