Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index


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 gif, we define a concrete class called BinaryHeap for this purpose.

Figure: Object class hierarchy

Program gif introduces the BinaryHeap class. The BinaryHeap class extends the AbstractContainer class introduced in Program gif and it implements the PriorityQueue interface defined in Program gif.

Program: BinaryHeap fields.

next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.