PowerPoint Presentation
Heaps
Chapter 17
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Contents
The ADT Heap
An Array-Based Implementation of a Heap
A Heap Implementation of the ADT Priority Queue
Heap Sort
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The ADT Heap
Definition
A heap is a complete binary tree that either is empty … or …
It’s root
Contains a value greater than or equal to the value in each of its children, and
Has heaps as its subtrees
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The ADT Heap
FIGURE 17-1 (a) A maxheap and (b) a minheap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The ADT Heap
FIGURE 17-2 UML diagram for the class Heap
View interface, Listing 17-1
.htm code listing files must be in the same folder as the .ppt files for these links to work
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Array-Based Implementation
of a Heap
FIGURE 17-3 (a) Level-by-level numbering of a complete binary tree; (b) its array-based implementation
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
FIGURE 17-4 (a) Disjoint heaps after
removing the heap’s root;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
FIGURE 17-4 (b) a semiheap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
FIGURE 17-4 (c) the restored heap
View algorithm to make this conversion, Listing 17-A
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
FIGURE 17-5 The array representation of
(a) the heap in Figure 17-4 a;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
FIGURE 17-5 The array representation of
(b) the semiheap in
Figure 17-4 b;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
FIGURE 17-5 The array representation of
(c) the restored heap in
Figure 17-4 c
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
FIGURE 17-6 Recursive calls to heapRebuild
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
FIGURE 17-7 Insertion into a heap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
Pseudocode for add
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The Implementation
The header file for class ArrayMaxHeap
An array-based implementation of the ADT heap
View Listing 17-2.
This heap is a maxheap.
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The Implementation
Definition of constructor
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The Implementation
FIGURE 17-8 (a) The initial contents of an array;
(b) the array’s corresponding complete binary tree
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The Implementation
FIGURE 17-9 Transforming an array into a heap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The Implementation
FIGURE 17-9 Transforming an array into a heap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The Implementation
Method heapCreate
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The Implementation
Method peekTop
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Heap Implementation of the ADT Priority Queue
Using a heap to define a priority queue results in a more time-efficient implementation
Listing 17-3 contains a header file for a class of priority queues.
View implementation, Listing 17-4
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Heap Sort
FIGURE 17-10 Heap sort partitions an array
into two regions
View heap sort algorithm, Listing 17-B
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Heap Sort
FIGURE 17-11 A trace of heap sort, beginning
with the heap in Figure 17-9
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Heap Sort
FIGURE 17-11 A trace of heap sort, beginning
with the heap in Figure 17-9
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Heap Sort
FIGURE 17-11 A trace of heap sort, beginning
with the heap in Figure 17-9
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Heap Sort
FIGURE 17-11 A trace of heap sort, beginning
with the heap in Figure 17-9
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
End
Chapter 17
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013