Red-Black Trees

Implement a priority queue using an OrderedLinkedList instead of a heap. Give the worst-case running time of each of your methods.

After doing Problem 14.21, rewrite the Heap class to handle only heaps of doubles. Use an array rather than an ArrayList. Your implementation of heapsort should be in place. (Hint: Recall Figure 8-7.)

Write a DisjointSetCluster class that uses an ArrayList of Sets instead of the up-tree data structure described in Section 14.2. Provide the methods inSameSet() and mergeSets(). What is the running time of these operation?

Suppose Figure 14-23 is the entire digital search tree for a game of Ghost. If your opponent starts the game with 'g,' why is 'r' not a wise response? Modify the program to take advantage of this information.