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

c. Write an implementation that uses these algorithms, using the

protocol in Figure 6.1.

d. Write an implementation that uses these algorithms, using the

standard SortedSet protocol.

A priority queue can be implemented by using a sorted array (as in
Exercise 6.25). Do the following:
a.

6.26

Describe the algorithms for findMin , deleteMin , and insert .

b. What is the Big-Oh running time for each of findMin , deleteMin ,

and insert using these algorithms?

c. Write an implementation that uses these algorithms.

A priority queue can be implemented by storing items in an unsorted
array and inserting items in the next available location. Do the following:
a.

6.27

Describe the algorithms for findMin , deleteMin , and insert .

b. What is the Big-Oh running time for each of findMin , deleteMin ,

and insert using these algorithms?

c. Write an implementation that uses these algorithms.

By adding an extra data member to the priority queue class in
Exercise 6.27, you can implement both insert and findMin in con-
stant time. The extra data member maintains the array position
where the minimum is stored. However, deleteMin is still expen-
sive. Do the following:
a.

6.28

Describe the algorithms for insert , findMin , and deleteMin .

b. What is the Big-Oh running time for deleteMin ?

c. Write an implementation that uses these algorithms.

By maintaining the invariant that the elements in the priority queue
are sorted in nonincreasing order (that is, the largest item is first, the
smallest is last), you can implement both findMin and deleteMin in
constant time. However, insert is expensive. Do the following:
a.

6.29

Describe the algorithms for insert , findMin , and deleteMin .

b. What is the Big-Oh running time for insert ?

c. Write an implementation that uses these algorithms.

A double-ended priority queue allows access to both the minimum
and maximum elements. In other words, all of the following are sup-
ported: findMin , deleteMin , findMax , and deleteMax . Do the following:
a.

6.30

Describe the algorithms for insert , findMin , deleteMin , findMax ,
and deleteMax .

b. What is the Big-Oh running time for each of findMin , deleteMin ,

findMax , deleteMax , and insert using these algorithms?

c. Write an implementation that uses these algorithms.