Trees - Data Structures and Abstractions with Java - page 588

/** Detects whether this heap is empty.
@return true if the heap is empty, else returns false */
public boolean isEmpty();

/** Gets the size of this heap.
@return the number of entries currently in the heap */
public int getSize();

/** Removes all entries from this heap. */
public void clear();
} // end MaxHeapInterface

If you place items into a maxheap and then remove them, you will get the items in descending
order. Thus, we can use a heap to sort an array, as you will see in Chapter 26.

Question 16 Does a maxheap that contains a given set of objects have a unique root? Jus-
tify your answer by using the maxheap in Figure 23-20a as an example.

Question 17 Is a maxheap that contains a given set of objects unique? Justify your answer
by using the maxheap in Figure 23-20a as an example.

23.33

Priority queues. We can use a heap to implement the ADT priority queue. Assuming that the
class MaxHeap implements MaxHeapInterface , a class that implements the priority queue as an
adapter class begins as given in Listing 23-7. Recall that we defined PriorityQueueInterface in
Segment 10.19 of Chapter 10.

LISTING 23-7

The beginning of the class PriorityQueue

public class PriorityQueue<T extends Comparable<? super T>>
implements PriorityQueueInterface<T>

{

private MaxHeapInterface<T> pq;

public PriorityQueue()
{

pq = new MaxHeap<T>();
} // end default constructor

public void add(T newEntry)
{

pq.add(newEntry);
} // end add
< Implementations of remove , peek , isEmpty , getSize , and clear are here. >
. . .
} // end PriorityQueue

Alternatively, the class MaxHeap could implement PriorityQueueInterface . We then could
define a priority queue of strings, as follows:

PriorityQueueInterface<String> pq = new MaxHeap<String> ();