Java Reference
In-Depth Information
When a collection of objects is organized by importance or priority, we call
this a priority queue. A normal queue data structure will not implement a prior-
ity queue efficiently because search for the element with highest priority will take
(n) time. A list, whether sorted or not, will also require (n) time for either in-
sertion or removal. A BST that organizes records by priority could be used, with the
total of n inserts and n remove operations requiring (n log n) time in the average
case. However, there is always the possibility that the BST will become unbal-
anced, leading to bad performance. Instead, we would like to find a data structure
that is guaranteed to have good performance for this special application.
This section presents the heap
4
data structure. A heap is defined by two prop-
erties. First, it is a complete binary tree, so heaps are nearly always implemented
using the array representation for complete binary trees presented in Section 5.3.3.
Second, the values stored in a heap are partially ordered. This means that there is
a relationship between the value stored at any node and the values of its children.
There are two variants of the heap, depending on the definition of this relationship.
A max-heap has the property that every node stores a value that is greater than
or equal to the value of either of its children. Because the root has a value greater
than or equal to its children, which in turn have values greater than or equal to their
children, the root stores the maximum of all values in the tree.
A min-heap has the property that every node stores a value that is less than
or equal to that of its children. Because the root has a value less than or equal to
its children, which in turn have values less than or equal to their children, the root
stores the minimum of all values in the tree.
Note that there is no necessary relationship between the value of a node and that
of its sibling in either the min-heap or the max-heap. For example, it is possible that
the values for all nodes in the left subtree of the root are greater than the values for
every node of the right subtree. We can contrast BSTs and heaps by the strength of
their ordering relationships. A BST defines a total order on its nodes in that, given
the positions for any two nodes in the tree, the one to the “left” (equivalently, the
one appearing earlier in an inorder traversal) has a smaller key value than the one
to the “right.” In contrast, a heap implements a partial order. Given their positions,
we can determine the relative order for the key values of two nodes in the heap only
if one is a descendant of the other.
Min-heaps and max-heaps both have their uses. For example, the Heapsort
of Section 7.6 uses the max-heap, while the Replacement Selection algorithm of
Section 8.5.2 uses a min-heap. The examples in the rest of this section will use a
max-heap.
Be careful not to confuse the logical representation of a heap with its physical
implementation by means of the array-based complete binary tree. The two are not
4
The term “heap” is also sometimes used to refer to a memory pool. See Section 12.3.
