1
$\begingroup$

I can't answer this question. It seems simple but I really don't know how to approach it. Here it is:

A priority queue is said to be stable if deletions of items with equal priority value occur in the order in which they were inserted. Which of the following priority queue structures are stable:

  • linked lists ordered in increasing priority (key)
  • balanced search trees (e.g., 2-3 trees)
  • heaps
  • leftist heaps

Explain why, or give counter-examples.

I don't need a full solution just a way to approach this problem. I would prefer to solve it on my own.

$\endgroup$
  • 4
    $\begingroup$ What have you tried? Have you tried running the algorithm by hand on some small examples? Based on those examples, do you have any conjecture about which ones are stable and which ones aren't? For the ones you suspect are stable, have you tried proving that it? $\endgroup$ – D.W. Oct 27 '13 at 2:23
  • $\begingroup$ @D.W. Turn into an answer? $\endgroup$ – Yuval Filmus Oct 27 '13 at 7:46
  • $\begingroup$ The answer depends on the specific implementations, in particular how they deal with duplicate keys (the usual textbook treatments assume pairwise distinct keys). $\endgroup$ – Raphael Dec 8 '14 at 21:41
2
$\begingroup$

Here's how I would suggest that you approach the problem. Try running each data structure by hand on some small examples. Then, based on those examples, see if you can form any conjecture about which data structures are stable and which ones aren't. For the ones you suspect are stable, try proving it. For the ones that you suspect are not stable, try to come up with a counterexample to demonstrate that they're not stable.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.