Binary Trees and Heap Implementation in Java
CSE 12 – Basic
Data Structures
Cynthia Bailey Lee
Some slides and figures
adapted from Paul Kube’s CSE
12
CS2 in Java Peer Instruction
Materials by
Cynthia Lee
is licensed
under a
Creative Commons
Attribution-NonCommercial 4.0
International License
.
Based on a work
at
http://peerinstruction4cs.org
.
Permissions beyond the scope of this
license may be available
at
http://peerinstruction4cs.org
.
Today’s Topics
1.
Heap implementation issues
Heap uniqueness
Heapsort in place
HW suggestions
2.
Back to generic binary trees
In-order traversal
Pre-order traversal
Post-order traversal
Level-order traversal (also called “breadth-first”)
2
Reading quiz!
1. A node in a binary tree may have
___ children
A.
0
B.
1
C.
2
D.
3
E.
Other/none of the above/more than
one of the above
Reading quiz!
2. A preorder traversal visits the current
node, performs a preorder traversal of
its ___ subtree and then performs a
preorder traversal of the its ___ subtree.
A.
right, right
B.
left, right
C.
left, left
D.
right, left
Reading quiz!
3. A full binary tree is a tree in which
every node other than the leaves has
____ children.
A.
0
B.
1
C.
2
D.
3
E.
Other/none of the above/more than
one of the above
Reading quiz!
Heap uniqueness
TRUE OR FALSE
There is only one configuration of a valid
min-heap containing the elements {34, 22,3, 9, 18}
A.
TRUE
B.
FALSE
Heap outcomes by insert order
Create a MIN-heap by inserting the elements, one by
one, in the order given below for the
first letter of your last
name
:
A-F: {3, 9, 18, 22, 34}
G-L: {3, 33, 18, 9, 34}
M-R: {9, 22, 18, 3, 34}
S-Z: {18, 22, 3, 9, 34}Heap outcomes by insert order
Create a MIN-heap by inserting the elements, one by
one, in the order given below for the
first letter of your last
name
:
A-F: {18, 9, 34, 3, 22}
G-L: {3, 18, 22, 9, 34}
M-R: {22, 9, 34, 3, 18}
S-Z: {34, 3, 9, 18, 22}How many distinct min-heaps are
possible for the elements {3, 9, 18,22, 34} ?
A.
1
B.
2-4
C.
5-8
D.
5! (5 factorial)
E.
Other/none/more
Heapsort
Heapsort is super easy
1.
Insert unsorted elements one at a time
into a heap until all are added
2.
Remove them from the heap one at a
time. We will always be removing the
next biggest[smallest] item from the
max-heap[min-heap], so the items come
out in sorted order!
THAT’S IT!
Example: using heapsort to print an
array in sorted order
(note: this is
not
the in-
place version you need for HW)
public static void printSorted(String[] unsortedlist)
{Heap<String> heap = new Heap<String>();
for (int i=0; i<unsortedlist.length; i++) {heap.add(unsortedlist[i]);
}
while (!heap.isEmpty()) {System.out.println(heap.remove());
}
}
Implementing heapsort
Devil’s in the details
We can do the entire heapsort
in place in one array
Unlike mergesort, we don’t need a
separate array for our workspace
We can do it all in place in one array (the
same array we were given as input)
Build heap by inserting
elements one at a time:
Sort array by removing
elements one at a time:
Build heap by inserting elements
one at a time IN PLACE:
Sort array by removing elements
one at a time IN PLACE:
Important tip!
The in-place approach will not work if your
test to see if index
i
is past the end of the
heap is to check if
heaparray[i]
is null.
Things will be in the array that are NOT in
the heap!
You need to keep track of an
int size
(in addition to an
int capacity
) in order
to check where the heap ends!
Binary tree traversals
Binary trees
Recall from last time, a binary tree is any
tree where each node has 0, 1, or 2
children
That’s the only restriction
Recall: heaps are a special case of binary
trees, and they have two additional
restrictions
Trees vs. Lists
Lists have an
obvious ordering
1
st
element is
first, 2
nd
element
is second, …
Trees don’t
More than one
reasonable
order
Pre-order traversal
preorder(node) { if (node != null){visit this node
preorder(node.left)
preorder(node.right)
}
}
A.
D B E A F C G
B.
A B D E C F G
C.
A B C D E F G
D.
D E B F G C A
E.
Other/none/more
Post-order traversal
postorder(node) { if (node != null){postorder(node.left)
postorder(node.right)
visit this node
}
}
A.
D B E A F C G
B.
A B D E C F G
C.
A B C D E F G
D.
D E B F G C A
E.
Other/none/more
In-order traversal
inorder(node) { if (node != null){inorder(node.left)
visit this node
inorder(node.right)
}
}
A.
D B E A F C G
B.
A B D E C F G
C.
A B C D E F G
D.
D E B F G C A
E.
Other/none/more
Explore the concepts of binary trees, heap implementation, and traversal techniques in Java through engaging peer instruction materials by Cynthia Lee. Learn about heap uniqueness, in-place heapsort, and generic binary trees. Test your knowledge with reading quizzes and analyze heap outcomes based on insert order. Interactive content makes learning data structures fun and informative.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Creative Commons License CS2 in Java Peer Instruction Materials by Cynthia Lee is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Based on a work at http://peerinstruction4cs.org. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org. CSE 12 Basic Data Structures Cynthia Bailey Lee Some slides and figures adapted from Paul Kube s CSE 12
2 Today s Topics 1. Heap implementation issues Heap uniqueness Heapsort in place HW suggestions 2. Back to generic binary trees In-order traversal Pre-order traversal Post-order traversal Level-order traversal (also called breadth-first )
Reading quiz! 1. A node in a binary tree may have ___ children A. 0 B. 1 C. 2 D. 3 E. Other/none of the above/more than one of the above
Reading quiz! 2. A preorder traversal visits the current node, performs a preorder traversal of its ___ subtree and then performs a preorder traversal of the its ___ subtree. A. right, right B. left, right C. left, left D. right, left
Reading quiz! 3. A full binary tree is a tree in which every node other than the leaves has ____ children. A. 0 B. 1 C. 2 D. 3 E. Other/none of the above/more than one of the above
TRUE OR FALSE There is only one configuration of a valid min-heap containing the elements {34, 22, 3, 9, 18} A. TRUE B. FALSE
Heap outcomes by insert order Create a MIN-heap by inserting the elements, one by one, in the order given below for the first letter of your last name: A-F: {3, 9, 18, 22, 34} G-L: {3, 33, 18, 9, 34} M-R: {9, 22, 18, 3, 34} S-Z: {18, 22, 3, 9, 34}
Heap outcomes by insert order Create a MIN-heap by inserting the elements, one by one, in the order given below for the first letter of your last name: A-F: {18, 9, 34, 3, 22} G-L: {3, 18, 22, 9, 34} M-R: {22, 9, 34, 3, 18} S-Z: {34, 3, 9, 18, 22}
How many distinct min-heaps are possible for the elements {3, 9, 18, 22, 34} ? A. 1 B. 2-4 C. 5-8 D. 5! (5 factorial) E. Other/none/more
Heapsort is super easy 1. Insert unsorted elements one at a time into a heap until all are added 2. Remove them from the heap one at a time. We will always be removing the next biggest[smallest] item from the max-heap[min-heap], so the items come out in sorted order! THAT S IT!
Example: using heapsort to print an array in sorted order (note: this is not the in- place version you need for HW) public static void printSorted(String[] unsortedlist) { Heap<String> heap = new Heap<String>(); for (int i=0; i<unsortedlist.length; i++) { heap.add(unsortedlist[i]); } while (!heap.isEmpty()) { System.out.println(heap.remove()); } }
Implementing heapsort Devil s in the details
We can do the entire heapsort in place in one array Unlike mergesort, we don t need a separate array for our workspace We can do it all in place in one array (the same array we were given as input)
Build heap by inserting elements one at a time:
Sort array by removing elements one at a time:
Build heap by inserting elements one at a time IN PLACE:
Sort array by removing elements one at a time IN PLACE:
Important tip! The in-place approach will not work if your test to see if index i is past the end of the heap is to check if heaparray[i] is null. Things will be in the array that are NOT in the heap! You need to keep track of an int size (in addition to an int capacity) in order to check where the heap ends!
Binary trees Recall from last time, a binary tree is any tree where each node has 0, 1, or 2 children That s the only restriction Recall: heaps are a special case of binary trees, and they have two additional restrictions
Trees vs. Lists Lists have an obvious ordering 1st element is first, 2nd element is second, Trees don t More than one reasonable order
Pre-order traversal preorder(node) { if (node != null){ visit this node preorder(node.left) preorder(node.right) } } A. D B E A F C G B. A B D E C F G C. A B C D E F G D. D E B F G C A E. Other/none/more
Post-order traversal postorder(node) { if (node != null){ postorder(node.left) postorder(node.right) visit this node } } A. D B E A F C G B. A B D E C F G C. A B C D E F G D. D E B F G C A E. Other/none/more
In-order traversal inorder(node) { if (node != null){ inorder(node.left) visit this node inorder(node.right) } } A. D B E A F C G B. A B D E C F G C. A B C D E F G D. D E B F G C A E. Other/none/more
