Heaps

Download Report

Transcript Heaps 

Chapter 17
Heaps
CS 302 - Data Structures
Mehmet H Gunes
Modified from authors’ slides
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
Complete Binary Tree
(1) A binary tree that is either full or full through
the next-to-last level
(2) The last level is full from left to right
(i.e., leaves are as far to the left as possible)
Complete Binary Tree
What is a Heap?
A heap is a binary tree that satisfies these
special SHAPE and ORDER properties:
– Its shape must be a complete binary tree.
– For each node in the heap, the value stored in
that node is greater than or equal to the value in
each of its children.
5
Are these Both Heaps?
treePtr
50
C
A
20
T
18
30
10
6
Is this a Heap?
tree
70
12
60
40
30
8
10
7
Unique?
8
Where is the Largest Element in a Heap Always Found?
tree
70
12
60
40
30
8
9
We Can Number the Nodes Left to Right by Level This Way
tree
70
0
60
12
1
2
40
30
8
3
4
5
10
And use the Numbers as Array Indexes to Store the Heap
tree.nodes
[0]
70
[1]
60
[2]
[3]
tree
70
0
12
40
60
12
1
2
[4]
30
40
30
8
[5]
8
3
4
5
[6]
11
With Array Representation
• For any node tree.nodes[index]
– its left child is in
• tree.nodes[index*2 + 1]
– right child is in
• tree.nodes[index*2 + 2]
– its parent is in
• tree.nodes[(index – 1)/2]
Leaf nodes:
tree.nodes[numElements/2]
to
tree.nodes[numElements - 1]
12
The ADT Heap
• (a) A maxheap and
(b) a minheap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The ADT Heap
• UML diagram for the class Heap
View interface,
Listing 17-1
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Array-Based Implementation of a Heap
• (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
• (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
• (b) a semiheap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
• (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
Reheap Down
bottom
19
Algorithms for Array-Based Heap Operations
• The array representation the heap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
• The array representation of
the semiheap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
• The array representation of
the restored heap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
• Recursive calls to heapRebuild
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Algorithms for Array-Based Heap Operations
• Insertion into a heap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Reheap Up
bottom
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
• (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
• Transforming an array into a heap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The Implementation
• Transforming an array into a heap
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Building a Heap:
4
14
4
4
1
3
8
7
5
1
6
16 9
10 7
2
14
4
8
9
8
7
7
2
14
8
7
16 9
3
3
10 7
14
2
4
8
9
8
7
5
6
16 9
0
4
4
16
1
10
9
1
6
10
i=0
2
8
5
0
1
7
2
0
1
4
1
3
3
8
0
2
i=1
3
10 14
4
4
9
9
0
2
8
16
i=2
1
2
2
i=3
1
7
3
i=4
0
3
1
2
16
5
6
16 9
3
10
3
7
2
14
1
8
9
8
1
2
14
4
5
6
7
9
3
10
3
7
2
8
8
9
4
1
4
5
6
7
9
3
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
• 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
• 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
• 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
• 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
• 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