Java Reference
In-Depth Information
FIGURE 23-20
(a) A maxheap and (b) a minheap that contain the same values
(b)
(a)
9
1
2
4
8
6
3
2
3
7
5
7
8
5
1
9
4
6
Minheap
Maxheap
The root of a maxheap contains the largest object in the heap. Notice that the subtrees of any
node in a maxheap are also maxheaps. Although we will focus on maxheaps, minheaps behave in
an analogous fashion.
Note:
A maxheap is a complete binary tree such that each node in the tree contains a
Comparable
object that is greater than or equal to the objects in the node's descendants.
23.32
Operations.
In addition to typical ADT operations such as
add
,
isEmpty
,
getSize
, and
clear
, a heap
has operations that retrieve and remove the object in its root. This object is either the largest or the
smallest object in the heap, depending on whether we have a maxheap or a minheap. This characteris-
tic enables us to use a heap to implement the ADT priority queue, as you will see in the next segment.
The Java interface in Listing 23-6 specifies operations for a maxheap.
LISTING 23-6
An interface for a maxheap
public interface
MaxHeapInterface<T
extends
Comparable<?
super
T>>
{
/** Adds a new entry to this heap.
@param newEntry an object to be added */
public void
add(T newEntry);
/** Removes and returns the largest item in this heap.
@return either the largest object in the heap or,
if the heap is empty before the operation, null */
public
T removeMax();
/** Retrieves the largest item in this heap.
@return either the largest object in the heap or,
if the heap is empty, null */
public
T getMax();
