|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
A binary heap is a heap-ordered complete binary tree which is implemented using an array. In a heap the smallest key is found at the root and since the root is always found in the first position of the array, finding the smallest key is a trivial operation in a binary heap.
In this section we describe the implementation
of a priority queue as a binary heap.
As shown in Figure 
,
we define a concrete class called BinaryHeap
for this purpose.
Figure: Object class hierarchy
Program introduces the BinaryHeap class.
The BinaryHeap class extends the AbstractContainer class
introduced in Program
and it implements the PriorityQueue interface
defined in Program .
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.
