Transcript Java Classes

A Heap
Implementation
Chapter 28
Slides by Steve Armstrong
LeTourneau University
Longview, TX
2007, Prentice Hall
Chapter Contents
•
•
•
•
•
•
Reprise: The ADT Heap
Using an Array to Represent a Heap
Adding an Entry
Removing the Root
Creating a Heap
Heapsort
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Reprise: The ADT Heap
• A complete binary tree
• Nodes contain Comparable objects
• In a maxheap
 Object in each node ≥ objects in descendants
• Note contrast of uses of the word "heap"
 The ADT heap
 The heap of the operating system from which
memory is allocated when new executes
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Reprise: The ADT Heap
• Interface used for implementation of
maxheap
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using an Array to Represent a Heap
Fig. 28-1 (a) A complete binary tree with its nodes
numbered in level order; (b) its representation as an array.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using an Array to Represent a Heap
• When a binary tree is complete
 Can use level-order traversal to store data in
consecutive locations of an array
• Enables easy location of the data in a
node's parent or children
 Parent of a node at i is found at i/2
(unless i is 1)
 Children of node at i found at indices
2i and 2i + 1
Click to view Java implementation
of class MaxHeap
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Class MaxHeap
Fig. 28-2 The steps in adding 85 to the
maxheap of Figure 28-1a
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Class MaxHeap
• Begin at next available position for a leaf
• Follow path from this leaf toward root until
find correct position for new entry
• As this is done
 Move entries from parent to child
 Makes room for new entry
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Adding an Entry
Fig. 28-3 A revision of steps shown in Fig.
28-2 to avoid swaps. …. continued →
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Adding an Entry
Fig. 28-3 (ctd.) A revision of steps shown
in Fig. 28-2 to avoid swaps.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Adding an Entry
Fig. 28-4 An array representation of the
steps in Fig. 28-3 … continued →
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Adding an Entry
Click to view
method add
Fig. 28-4 (ctd.) An array representation of
the steps in Fig. 28-3.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Removing the Root
Fig. 28-5 The steps to remove the entry in the root of the
maxheap of Fig. 28-3d
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Removing the Root
Fig. 28-6 The steps that transform a semiheap into
a heap without swaps.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Removing the Root
• To remove a heap's root
 Replace the root with heap's last child
• This forms a semiheap
• Then use the method reheap
 Transforms the semiheap to a heap
• View method removeMax
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Creating a Heap
Fig. 28-7 The steps in adding 20, 40, 30, 10,
90, and 70 to a heap.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Creating a Heap
Fig. 28-8 The steps in creating a heap by
using reheap. View use in constructor.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Heapsort
• Possible to use a heap to sort an array
• Place array items into a maxheap
• Then remove them
 Items will be in descending order
 Place them back into the original array and
they will be in order
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Heapsort
Fig. 28-9 A trace of heapsort (a – c)
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Heapsort
Fig. 28-9 A trace of heapsort (d – f)
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Heapsort
Fig. 28-9 A trace of heapsort (g – i)
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Heapsort
Fig. 28-9 A trace of heapsort (j – l)
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Heapsort
• View implementation of a heapSort
 Efficiency is O(n log n).
 However, quicksort is usually a better choice
• Note it also uses reheap
 View source code of reheap
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X