Consider any order, and suppose that for some .
Suppose that we switch the elements and Say that we switched between and
Let be the difference in average search cost (new cost minus old cost). When looking for which happens with probability
we have to pay more. When looking for which happens with probability
we have to pay less. So
In other words, the switch was beneficial. We conclude that the optimal arrangement is to store the elements in non-increasing order.
3. Let X be a set of n elements to be maintained as a linked list:...
I've posted 3 classes after the instruction that were given at start You will implement and test a PriorityQueue class, where the items of the priority queue are stored on a linked list. The material from Ch1 ~ 8 of the textbook can help you tremendously. You can get a lot of good information about implementing this assignment from chapter 8. There are couple notes about this assignment. 1. Using structure Node with a pointer point to Node structure to...