The collections api - Data Structures and Problem Solving Using Java - page 291

A median heap supports the following operations: insert , findKth ,
and removeKth . The last two find and remove, respectively, the K th
smallest element (where k is a parameter). The simplest implementa-
tion maintains the data in sorted order. Do the following:
a.

6.31

Describe the algorithms that can be used to support median heap
operations.

b. What is the Big-Oh running time for each of the basic operations

using these algorithms?

c. Write an implementation that uses these algorithms.

A MultiSet is like a Set , but allows duplicates. Consider the following
interface for a MultiSet :

6.32

public interface MultiSet<AnyType>
{
void add( AnyType x );
boolean contains( AnyType x );
int count( AnyType x );
boolean removeOne( AnyType x );
boolean removeAll( AnyType x );
void toArray( AnyType [] arr );
}

There are many ways to implement the MultiSet interface. A TreeMultiSet
stores items in sorted order. The data representation can be a TreeMap , in
which the key is an item that is in the multiset, and the value represents
the number of times the item is stored. Implement the TreeMultiSet , and
make sure toString is provided.

Write a program that reads strings from input and outputs them sorted,
by length, shortest string first. If a subset of input strings has the same
length, your program should output them in alphabetical order.

6.33

Collections.fill takes a List and a value , and places value in all posi-
tions in the list. Implement fill .

6.34

Collections.reverse takes a List and reverses its contents. Implement
reverse .

6.35

Write a method that removes every other element in a List . Your rou-
tine should run in linear time and use constant extra space if the List
is a LinkedList .

6.36

Write a method that takes a Map<String,String> as a parameter and
returns a new Map<String,String> in which keys and values are
swapped. Throw an exception if there are duplicate values in the map
that is passed as a parameter.

6.37