Chapter 17 – Tree Structures
Chapter Goals
 To study trees and binary trees
 To understand how binary search trees can implement sets
 To learn how redblack trees provide performance guarantees for set operations
 To choose appropriate methods for tree traversal
 To become familiar with the heap data structure
 To use heaps for implementing priority queues and for sorting
Basic Tree Concepts
 A family tree shows the descendants of a common ancestor.
 In computer science, a tree is a hierarchical data structure composed of nodes.
 Each node has a sequence of child nodes.
 The root is the node with no parent.
 A leaf is a node with no children.
Basic Tree Concepts
 British royal family tree
Figure 1 A Family Tree
Basic Tree Concepts
 Some common tree terms:
Trees in Computer Science
Figure 2 A Directory Tree
Gifure 3 An Inheritance Tree
Basic Tree Concepts
 A tree class holds a reference to a root node.
 Each node holds:
 A data item
 A list of references to the child nodes
 A Tree class:
public class Tree { private Node root; class Node { public Object data; public List<Node> children; } public Tree(Object rootData) { root = new Node(); root.data = rootData; root.children = new ArrayList<Node>(); } public void addSubtree(Tree subtree) { root.children.add(subtree.root); } . . . }
Basic Tree Concepts
 When computing tree properties, it is common to recursively visit smaller and smaller subtrees.
 Size of tree with root r whose children are c_{1} ... c_{k}
 size(r) = 1 + size(c_{1}) + ... + size(c_{k})
Basic Tree Concepts
 The size method in the Tree class:
public class Tree { . . . public int size() { if (root == null) { return 0; } else { return root.size(); } } }
 Recursive helper method in the Node class:
class Node { . . . public int size() { int sum = 0; for (Node child : children) { sum = sum + child.size(); } return 1 + sum; } }
Self Check 17.1
What are the paths starting with Anne in the tree shown in Figure 1?
Answer:
There are four paths:
Anne
Anne, Peter
Anne, Zara
Anne, Peter, Savannah
Self Check 17.2
What are the roots of the subtrees consisting of 3 nodes in the tree shown in Figure 1?
 Answer: There are three subtrees with three nodesâ they have roots Charles, Andrew, and Edward.
Self Check 17.3
What is the height of the subtree with root Anne? Answer: 3
Self Check 17.4
What are all possible shapes of trees of height 3 with two leaves?
Answer:
Self Check 17.5
Describe a recursive algorithm for counting all leaves in a tree
Answer:
If n is a leaf, the leaf count is 1. Otherwise Let c_{1} ... c_{n} be the children of n. The leaf count is leafCount(c_{1}) + ...+ leafCount(c_{n}).
Self Check 17.6
Using the public interface of the Tree class in this section, construct a tree that is identical to the subtree with root Anne in Figure 1.
Answer:
Tree t1 = new Tree("Anne"); Tree t2 = new Tree("Peter"); t1.addSubtree(t2); Tree t3 = new Tree("Zara"); t1.addSubtree(t3); Tree t4 = new Tree("Savannah"); t2.addSubtree(t4);
Self Check 17.7
Is the size method of the Tree class recursive? Why or why not? Answer: It is not. However, it calls a recursive methodâthe size method of the Node class.
Binary Trees
In a binary tree, each node has a left and a right child node.
Binary Trees Examples  Decision Tree
 A decision tree contains
questions used
to decide among a
number of options.
 In a decision tree:
 Each nonleaf node contains a question
 The left subtree corresponds to a âyesâ answer
 The right subtree to a ânoâ answer
 Every node has either two children or no children
Binary Trees Examples  Decision Tree
Figure 4 A Decision Tree for an Animal Guessing Game
Binary Tree Examples  Huffman Tree
 In a Huffman tree:
 The leaves contain symbols that we want to encode.
 To encode a particular symbol:
 Walk along the path from the root to the leaf containing the symbol, and produce
 A zero for every left turn
 A one for every right turn
Binary Tree Examples  Huffman Tree
Figure 5 A Huffman Tree for Encoding the Thirteen Characters of Hawaiian Alphabet
Binary Tree Examples  Expression Tree
 An expression tree shows the order of evaluation in an arithmetic expression.
 The leaves of the expression trees contain numbers.
 Interior nodes contain the operators
 (3 + 4) * 5
 3 + 4 * 5
Figure 6 Expression Trees
Balanced Trees
In a balanced binary tree, each subtree has approximately the same number of nodes.
Balanced Trees
Figure 7 Balanced and Unbalanced Trees
Balanced Trees
 A binary tree of height h can have up to n = 2^{h} â 1 nodes.
 A completely filled binary tree of height 4 has 1 + 2 + 4 + 8 = 15 = 2^{4} â 1 nodes.
 For a completely filled binary tree: h = log_{2}(n + 1)
 For a balanced tree: h ≈ log_{2}(n)
 Example: the height of a balanced binary tree with1,000 nodes
 Approximately 10 (because 1000 ≈ 1024 = 2^{10}).
 Example: the height of a balanced binary tree with1,000,000 nodes
 approximately 20 (because 10^{6} ≈ 2^{20})
 You can find any element in this tree in about 20 steps
A Binary Tree Implementation
 Binary tree node has a reference:
 to a right child
 to a left child
 either can be null
 Leaf: node in which both children are null.
A Binary Tree Implementation
 BinaryTree class:
public class BinaryTree { private Node root; public BinaryTree() { root = null; } // An empty tree public BinaryTree(Object rootData, BinaryTree left, BinaryTree right) { root = new Node(); root.data = rootData; root.left = left.root; root.right = right.root; } class Node { public Object data; public Node left; public Node right; } . . . }
A Binary Tree Implementation
 To find the height of a binary tree t with left and right children l and r
 Take the maximum height of the two children and add 1
 height(t) = 1 + max(height(l), height(r))
A Binary Tree Implementation
 Make a static recursive helper method height in the Tree class:
public class BinaryTree { . . . private static int height(Node n) { if (n == null) { return 0; } else { return 1 + Math.max(height(n.left), height(n.right)); } } . . . }
 Provide a public height method in the Tree class:
public class BinaryTree { . . . public int height() { return height(root); } }
Self Check 17.8
Encode ALOHA, using the Huffman code in Figure 5.
Answer:
A=10, L=0000, O=001, H=0001, therefore ALOHA = 100000001000110.
Self Check 17.9
In an expression tree, where is the operator stored that gets executed last? Answer: In the root.
Self Check 17.10
What is the expression tree for the expression 3 â 4 â 5?
Answer:
Self Check 17.11
How many leaves do the binary trees in Figure 4, Figure 5, and Figure 6 have? How many interior nodes?
Answer:
Figure 4: 6 leaves, 5 interior nodes.
Figure 5: 13 leaves, 12 interior nodes.
Figure 6: 3 leaves, 2 interior nodes.
You might guess from these data that the number of leaves always equals the number of interior nodes + 1. That is true if all interior nodes have two children, but it is false otherwiseâconsider this tree whose root only has one child.
Self Check 17.12
Show how the recursive height helper method can be implemented as an instance method of the Node class. What is the disadvantage of that approach?
Answer:
public class BinaryTree { . . . public int height() { if (root == null) { return 0; } else { return root.height(); } } class Node { . . . public int height() { int leftHeight = 0; if (left != null) { leftHeight = left.height(); } int rightHeight = 0; if (right != null) { rightHeight = right.height(); } return 1 + Math.max(leftHeight, rightHeight); } } }
This solution requires three null checks; the solution in Section 17.2.3 only requires one.
Binary Search Trees
 All nodes in a binary
search tree fulfill this
property:
 The descendants to the left have smaller data values than the node data value,
 The
descendants to the
right have larger
data values.
Binary Search Trees
Binary Search Trees
Binary Search Trees
 The data variable must have type Comparable.
 BinarySearchTree
public class BinarySearchTree { private Node root; public BinarySearchTree() { . . . } public void add(Comparable obj) { . . . } . . . class Node { public Comparable data; public Node left; public Node right; public void addNode(Node newNode) { . . . } . . . } }
Binary Search Trees  Insertion
 Algorithm to insert data:
 If you encounter a nonnull node reference, look at its data value.
 If the data value of that node is larger than the value you want to insert,
 Continue the process with the left child.
 If the nodeâs data value is smaller than the one you want to insert,
 Continue the process with the right child.
 If the nodeâs data value is the same as the one you want to insert,
 You are done. A set does not store duplicate values.
 If you encounter a null node reference, replace it with the new node.
Binary Search Trees  Insertion
 add method in BinarySearchTree:
public void add(Comparable obj) { Node newNode = new Node(); newNode.data = obj; newNode.left = null; newNode.right = null; if (root == null) { root = newNode; } else { root.addNode(newNode); } }
 addNode method of the Node class:
class Node { . . . public void addNode(Node newNode) { int comp = newNode.data.compareTo(data); if (comp < 0) { if (left == null) { left = newNode; } else { left.addNode(newNode); } } else if (comp > 0) { if (right == null) { right = newNode; } else { right.addNode(newNode); } } } . . . }
Binary Search Trees  Removal
 First, find the node.
 Case 1: The node has no children
 Set the link in the parent to null
 Set the link in the parent to null
 Case 2: The node has 1 child
 Modify the parent link to the node to point to the child node
Figure 14 Removing a Node with One Child
 Modify the parent link to the node to point to the child node
Binary Search Trees  Removal
 Case 3: The node has 2 children
 Replace it with the
smallest node of the
right subtree
 Replace it with the
smallest node of the
right subtree
Binary Search Trees  Efficiency of the Operations
 If a binary search
tree is balanced, then
adding, locating, or
removing an element
takes O(log(n)) time.
section_3/BinarySearchTree.java
Self Check 17.13
What is the difference between a tree, a binary tree, and a balanced binary tree? Answer: In a tree, each node can have any number of children. In a binary tree, a node has at most two children. In a balanced binary tree, all nodes have approximately as many descendants to the left as to the right.
Self Check 17.14
Are the left and right children of a binary search tree always binary search trees? Why or why not? Answer: Yesââbecause the binary search condition holds for all nodes of the tree, it holds for all nodes of the subtrees.
Self Check 17. 15
Draw all binary search trees containing data values A, B, and C.
Answer:
Self Check 17.16
Give an example of a string that, when inserted into the tree of Figure 12, becomes a right child of Romeo. Answer: For example, Sarah. Any string between Romeo and Tom will do.
Self Check 17.17
Trace the removal of the node âTomâ from the tree in Figure 12.
Answer:
âTomâ has a single child. That child replaces âTomâ in the parent âJulietâ.
Self Check 17.18
Trace the removal of the node âJulietâ from the tree in Figure 12.
Answer:
âJulietâ has two children. We look for the smallest child in the right subtree, âRomeoâ. The data replaces âJulietâ, and the node is removed from its parent âTomâ.
Tree Traversal  Inorder Traversal
 To print a Binary Search Tree in sorted order
Print the left subtree. Print the root data. Print the right subtree.
 This called an inorder traversal.
 Recursive helper method for printing the tree.
private static void print(Node parent) { if (parent == null) { return; } print(parent.left); System.out.print(parent.data + " "); print(parent.right); }
 Public print method starts the recursive process at the root:
public void print() { print(root); }
Preorder and Postorder Traversals
 Preorder
 Visit the root
 Visit left subtree
 Visit the right subtree
 Postorder
 Visit left subtree
 Visit the right subtree
 Visit the root
 A postorder traversal of an expression tree results in an expression in reverse Polish notation.
Preorder and Postorder Traversals
 Use postorder traversal to remove all directories from a directory tree.
 A directory must be empty before you can remove it
 A directory must be empty before you can remove it
 Use preorder traversal to copy a directory tree.
 Can have pre and postorder traversal for any tree.
 Only a binary tree has an inorder traversal.
The Visitor Pattern
 Visitor interface to define action to take when visiting the nodes:
public interface Visitor { void visit(Object data); }
 Preorder traversal with a Visitor:
private static void preorder(Node n, Visitor v) { if (n == null) { return; } v.visit(n.data); for (Node c : n.children) { preorder(c, v); } } public void preorder(Visitor v) { preorder(root, v); }
 You can also create visitors with inorder or postorder.
The Visitor Pattern
 Example: Count all the names with at most 5 letters.
public static void main(String[] args) { BinarySearchTree bst = . . .; class ShortNameCounter implements Visitor { public int counter = 0; public void visit(Object data) { if (data.toString().length() <= 5) { counter++; } } } ShortNameCounter v = new ShortNameCounter(); bst.inorder(v); System.out.println("Short names: " + v.counter); }
DepthFirst Search
 Iterative traversal can stop when a goal has been met.
 Depthfirst search uses a stack to track the nodes that it still needs to visit.
 Algorithm:
Push the root node on a stack. While the stack is not empty Pop the stack; let n be the popped node. Process n. Push the children of n on the stack, starting with the last one.
BreadthFirst Search
 Breadthfirst search first visits all nodes on the same level before visiting the children.
 Breathfirst search uses a queue.
 Modify the Visitor interface to return false when the traversal should stop
public interface Visitor { boolean visit(Object data); } public void breadthFirst(Visitor v) { if (root == null) { return; } Queue<Node> q = new LinkedList<Node>(); q.add(root); boolean more = true; while (more && q.size() > 0) { Node n = q.remove(); more = v.visit(n.data); if (more) { for (Node c : n.children) { q.add(c); } } } }
Tree Iterators
 The Java collection library has an iterator to process trees:
TreeSet<String> t = . . . Iterator<String> iter = t.iterator(); String first = iter.next(); String second = iter.next();
 A breadth first iterator:
class BreadthFirstIterator { private Queue<Node> q; public BreadthFirstIterator(Node root) { q = new LinkedList<Node>(); if (root != null) { q.add(root); } } public boolean hasNext() { return q.size() > 0; } public Object next() { Node n = q.remove(); for (Node c : n.children) { q.add(c); } return n.data; } }
Self Check 17.19
What are the inorder traversals of the two trees in Figure 6 on page 767? Answer: For both trees, the inorder traversal is 3 + 4 * 5.
Self Check 17.20
Are the trees in Figure 6 binary search trees? Answer: Noâfor example, consider the children of +. Even without looking up the Unicode values for 3, 4, and +, it is obvious that + isn't between 3 and 4.
Self Check 17.21
Why did we have to declare the variable v in the sample program in Section 17.4.4 as ShortNameCounter and not as Visitor? Answer: Because we need to call v.counter in order to retrieve the result.
Self Check 17.22
Consider this modification of the recursive inorder traversal. We want traversal to stop as soon as the visit method returns false for a node.public static void inorder(Node n, Visitor v) { if (n == 0) { return; } inorder(n.left, v); if (v.visit(n.data)) { inorder(n.right, v); } }Why doesn't that work?

Answer: When the method returns to its caller, the
caller can continue traversing the tree. For
example, suppose the tree is
Letâs assume that we want to stop visiting as soon as we encounter a zero, so visit returns false when it receives a zero. We first call inorder on the node containing 2. That calls inorder on the node containing 0, which calls inorder on the node containing â1. Then visit is called on 0, returning false. Therefore, inorder is not called on the node containing 1, and the inorder call on the node containing 0 is finished, returning to the inorder call on the root node. Now visit is called on 2, returning true, and the visitation continues, even though it shouldn't. See Exercise E17.10 for a fix.
Self Check 17.23
In what order are the nodes in Figure 17 visited if one pushes children on the stack from left to right instead of right to left? Answer: AGIHFBEDC
Self Check 17.24
What are the first eight visited nodes in the breadthfirst traversal of the tree in Figure 1? Answer: Thatâs the royal family tree, the first tree in the chapter: George V, Edward VIII, George VI, Mary, Henry, George, John, Elizabeth II.
RedBlack Trees
 A kind of binary search tree that rebalances itself after each insertion or removal.
 Guaranteed O(log(n)) efficiency.
 Additional requirements:
 Every node is colored red or black.
 The root is black.
 A red node cannot have a red child (the âno double redsâ rule).
 All paths from the root to a null have the same number of black nodes (the âequal exit costâ rule).
 Example
RedBlack Trees
Think of each node of a redblack tree as a toll booth. The total toll to each exit is the same.
RedBlack Trees
Figure 19 A Tree that Violates "Equal Exit Cost" Rule
Figure 20 A Tree that Violates the "No Double Red" Rule
RedBlack Trees
 The âequal exit costâ rule eliminates highly unbalanced trees.
 You canât have null references high up in the tree.
 The nodes that aren't near the leaves need to have two children.
 The âno double redsâ rule gives some flexibility to add nodes without having to restructure the tree all the time.
 Some paths can be a bit longer than others
 None can be longer than twice the black height.
RedBlack Trees
 Black height of a node:
 The cost of traveling on a path from a given node to a null
 The number of black nodes on the path
 Black height of the tree:
 The cost of traveling from the root to a null
 Tree with black height bh
 must have at least 2^{bh} â 1 nodes
 bh ≤ log(n + 1)
 The âno double redsâ rule says that the total height h of a tree is at most twice the black height:
 h ≤ 2 · bh ≤ 2 · log(n + 1)
 Traveling from the root to a null is O(log(n)).
RedBlack Trees  Insertion
 First insert the node as into a regular binary search tree:
 If it is the root, color it black
 Otherwise, color it red
 If the parent is black, it is a redblack tree.
 If the parent is red, need to fix the "double red" violation.
 We know the grandparent is black.
RedBlack Trees  Insertion
 Four possible configurations given black grandparent:
 Smallest, middle, and largest labeled n_{1}, n_{2}, n_{3}
 Their children are labeled in sorted order, starting with t_{1}
Figure 21 The Four Possible Configurations of a "Double Red"
RedBlack Trees  Insertion
 Move up the tree fixing any other "doublered" problems in the same way.
 If the troublesome red parent is the root,
 Turn it black
 That will add 1 to all paths, preserving "equal exit cost" rule
Figure 22 Fix the "doublered" by rearranging the nodes
RedBlack Trees  Insertion
 When the height of the binary search tree is h:
 Finding the insertion point takes at most h steps
 Fixing doublered violations takes at most h / 2
 Because we know h = O(log(n)), insertion is guaranteed O(log(n)) efficiency.
RedBlack Trees  Removal
 Before removing a node in a redblack tree, turn it red and fix any doubleblack and doublered violations.
 First remove the node as in a regular binary search tree.
 If the node to be removed is red, just remove it.
 If the node to be removed is black and has a child:
 Color that child black
 Color that child black
 Troublesome case is removal of a black leaf.
 Just removing it will cause an "equal exit cost" violation
 So turn it into a red node
RedBlack Trees  Removal
 To turn a black node into a red one:
 bubble up the cost
 Add one the the parent and subtract 1 from the children
 May result in a double black and negative red
 Transform in this manner
Figure 23 Eliinating a NegativeRed Node with a DoubleBlack Parent
RedBlack Trees  Removal
 Fixing a DoubleRed
Violation Also Fixes
a DoubleBlack
Grandparent
RedBlack Trees  Removal
 If a double black reaches the root, replace it with a regular black:
 Reduces the cost of all paths by 1
 Preserves the "equal exit cost" rule
Figure 25 Bubbling Up a DoubleBlack Node
RedBlack Trees Efficiency
Self Check 17.25
Consider the extreme example of a tree with only right children and at least three nodes. Why canât this be a redblack tree? Answer: The root must be black, and the second or third node must also be black, because of the âno double redsâ rule. The left null of the root has black height 1, but the null child of the next black node has black height 2.
Self Check 17.26
What are the shapes and colorings of all possible redblack trees that have four nodes? Answer:
Self Check 17.27
Why does Figure 21 show all possible configurations of a doublered violation? Answer: The top red node can be the left or right child of the black parent, and the bottom red node can be the left or right child of its (red) parent, yielding four configurations.
Self Check 17.28
When inserting an element, can there ever be a triplered violation in Figure 21? That is, can you have a red node with two red children? (For example, in the first tree, can t1 have a red root?) Answer: No. Look at the first tree. At the beginning, n_{2} must have been the inserted node. Because the tree was a valid redblack tree before insertion, t_{1} couldn't have had a red root. Now consider the step after one doublered removal. The parent of n_{2} in Figure 22 may be red, but then n_{2} can't have a red siblingâotherwise the tree would not have been a redblack tree.
Self Check 17.29
When removing an element, show that it is possible to have a triplered violation in Figure 23.
Answer: Consider this scenario, where X is the black
leaf to be removed.
Self Check 17.30
What happens to a triplered violation when the doublered fix is applied? Answer: It goes away. Suppose the sibling of the red grandchild in Figure 21 is also red. That means that one of the t_{i} has a red root. However, all of them become children of the black n_{1} and n_{3} in Figure 22.
Heaps
 A heap (minheap) :
 Binary tree
 Almost completely filled
 All nodes are filled in, except the last level
 may have some nodes missing toward the right
 All nodes fulfill the heap property
 The value of any node is less than or equal to the values of its descendants.
 The value of the root is the minimum of all all the values in the tree.
Heaps
Figure 26 An Almost Completely Filled Tree
Heaps
In an almost complete tree, all layers but one are completely filled.
Heaps
 The value of every node is smaller than all its descendants.
Figure 27A Heap
Heaps
Differences from a binary search tree
 The shape of a heap is very regular.
 Binary search trees can have arbitrary shapes.
 In a heap, the left and right subtrees both store elements that are larger than the root element.
 In a binary search tree, smaller elements are stored in the left subtree and larger elements are stored in the right subtree.
Heaps  Insertion
Algorithm to insert a node
 Add a vacant slot to the end of the tree.
 If the parent of the empty slot if it is larger than the element to be inserted:
 Demote the parent by moving the parent value into the vacant slot,
 Move the vacant slot up.
 Repeat this demotion as long as the parent of the vacant slot is larger than the element to be inserted.
 Insert the element into the vacant slot at this point,
 Either the vacant slot is at the root
 Or the parent of the vacant slot is smaller than the element to be inserted.
Heaps  Insertion Step 1
Heaps  Insertion Step 2
Heaps  Insertion Step 3
Heaps  Removing the Root
 The root contains the minimum of all the values in the heap
 Algorithm to remove the root
 Extract the root node value.
 Move the value of the last node of the heap into the root node,
 Remove the last node.
 One or both of the children of the root may now be smaller  violating the heap property
 Promote the smaller child of the root node.
 Repeat this process with the demoted child , promoting the smaller of its children.
 Continue until the demoted child has no smaller children.
 The heap property is now fulfilled again. This process is called âfixing the heapâ.
Heaps  Removing the Root Steps 1 and 2
Heaps  Removing the Root Step 3
Heaps  Efficiency
 Inserting or removing a heap element is an O(log(n)) operation.
 These operations visit at most h nodes (where h is the height of the tree)
 A tree of height h contains between 2^{h1} and 2^{h} nodes (n)
 2^{h1}≤ n < 2^{h}
 h â 1 ≤ log_{2}(n) < h
Heaps
 The regular layout of a heap makes it possible to store heap nodes efficiently in an array.
 Very efficient
 Store the first layer, then the second, and so o.n
 Leave the 0 element empty.
Figure 30 Storing a Heap in an Array
 The child nodes of the node with index i have index 2 • i and 2 • i + 1.
 The parent node of the node with index i has index i².
Heaps
 A maxheap has the largest element stored in the root.
 A minheap can be used to implement a priority queue.
section_6/MinHeap.java
section_6/WorkOrder.java
section_6/HeapDemo.java
Program Run:
priority=1, description=Fix broken sink priority=2, description=Order cleaning supplies priority=3, description=Shampoo carpets priority=6, description=Replace light bulb priority=7, description=Empty trash priority=8, description=Water plants priority=9, description=Clean coffee maker priority=10, description=Remove pencil sharpener shavings
Self Check 17.31
The software that controls the events in a user interface keeps the events in a data structure. Whenever an event such as a mouse move or repaint request occurs, the event is added. Events are retrieved according to their importance. What abstract data type is appropriate for this application? Answer: A priority queue is appropriate because we want to get the important events first, even if they have been inserted later.
Self Check 17.32
In an almostcomplete tree with 100 nodes, how many nodes are missing in the lowest level? Answer: 27. The next power of 2 greater than 100 is 128, and a completely filled tree has 127 nodes.
Self Check 17.33
If you traverse a heap in preorder, will the nodes be in sorted order? Answer: Generally not. For example, the heap in Figure 30 in preorder is 20 75 84 90 96 91 93 43 57 71.
Self Check 17.34
What is the heap that results from inserting 1 into the following? Answer:
Self Check 17.35
What is the result of removing the minimum from the following?
Answer:
The Heapsort Algorithm
 The heapsort
algorithm:
 Insert all elements into the heap
 Keep extracting the minimum.
 Heapsort is an O(n log(n)) algorithm.
Tree to Heap
Tree to Heap
 Better to use a maxheap rather than a minheap.
Self Check 17.36
Which algorithm requires less storage, heapsort or merge sort? Answer: Heapsort requires less storage because it doesn't need an auxiliary array.
Self Check 17.37
Why are the computations of the left child index and the right child index in the HeapSorter different than in MinHeap? Answer: The MinHeap wastes the 0 entry to make the formulas more intuitive. When sorting an array, we donât want to waste the 0 entry, so we adjust the formulas instead.
Self Check 17.38
What is the result of calling HeapSorter.fixHeap(a, 0, 4) where a contains 1 4 9 5 3?
Answer: In tree form, that is
Remember, itâs a maxheap!
Self Check 17.39
Suppose after turning the array into a heap, it is 9 4 5 1 3. What happens in the first iteration of the while loop in the sort method?
Answer:
The 9 is swapped with 3, and the heap is fixed up again, yielding
5 4 3 1  9.
Self Check 17.40
Does heapsort sort an array that is already sorted in O(n) time? Answer: Unfortunately not. The largest element is removed first, and it must be moved to the root, requiring O(log(n)) steps. The second largest element is still toward the end of the array, again requiring O(log(n)) steps, and so on.