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.

Improve this question
$\endgroup$
3
  • 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$ Commented Oct 27, 2013 at 2:23
  • $\begingroup$ @D.W. Turn into an answer? $\endgroup$ Commented Oct 27, 2013 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$ Commented Dec 8, 2014 at 21:41

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.