Problem Detail: 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.
Asked By : flashburn
Answered By : D.W.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16456
