Java Reference
In-Depth Information
chapter
21
the binary heap
T
he priority queue is a fundamental data structure that allows
access only to the minimum item. In this chapter we discuss one
implementation of the priority queue data structure, the elegant
binary heap
. The binary heap supports the insertion of new items and
the deletion of the minimum item in logarithmic worst-case time. It
uses only an array and is easy to implement.
In this chapter, we show
The basic properties of the binary heap
n
How the
insert
and
deleteMin
operations can be performed in
logarithmic time
n
A linear-time heap construction algorithm
n
A Java 5 implementation of class
PriorityQueue
n
An easily implemented sorting algorithm,
heapsort
,
that
runs in
O
(
N
log
N
) time but uses no extra memory
n
The use of heaps to implement external sorting
n
Search WWH ::
Custom Search