# Horstmann Chapter 17 # Chapter Goals • To study trees and binary trees
• To understand how binary search trees can implement sets
• To learn how red-black 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)
{
}
. . .
}```

# 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 c1 ... ck
• size(r) = 1 + size(c1) + ... + size(ck)

• # 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?

# Self Check 17.4

What are all possible shapes of trees of height 3 with two leaves? # Self Check 17.5

Describe a recursive algorithm for counting all leaves in a tree
```If n is a leaf, the leaf count is 1.
Otherwise
Let c1 ... cn be the children of n.
The leaf count is leafCount(c1) + ...+ leafCount(cn).```

# 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. ```Tree t1 = new Tree("Anne");
Tree t2 = new Tree("Peter");
Tree t3 = new Tree("Zara");
Tree t4 = new Tree("Savannah");

# 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 non-leaf 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 = 2h â 1 nodes.
• A completely filled binary tree of height 4 has 1 + 2 + 4 + 8 = 15 = 24 â 1 nodes. • For a completely filled binary tree: h = log2(n + 1)
• For a balanced tree: h ≈ log2(n)
• Example: the height of a balanced binary tree with1,000 nodes
• Approximately 10 (because 1000 ≈ 1024 = 210).
• Example: the height of a balanced binary tree with1,000,000 nodes
• approximately 20 (because 106 ≈ 220)
• 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. 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? # Self Check 17.11

How many leaves do the binary trees in Figure 4, Figure 5, and Figure 6 have? How many interior nodes?
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?
```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 non-null 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 • 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

# Binary Search Trees - Removal

• Case 3: The node has 2 children
• 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. # 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. # 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 • Use preorder traversal to copy a directory tree. • Can have pre- and post-order 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);
}```

# Depth-First Search

• Iterative traversal can stop when a goal has been met.
• Depth-first 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.``` • Breadth-first search first visits all nodes on the same level before visiting the children.
• Breath-first 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>();
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;
{
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? # Self Check 17.24

What are the first eight visited nodes in the breadth-first 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.

# Red-Black Trees

• A kind of binary search tree that rebalances itself after each insertion or removal.
• Guaranteed O(log(n)) efficiency.
• 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 # Red-Black Trees Think of each node of a red-black tree as a toll booth. The total toll to each exit is the same.

# Red-Black Trees Figure 19 A Tree that Violates "Equal Exit Cost" Rule Figure 20 A Tree that Violates the "No Double Red" Rule

# Red-Black 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.

# Red-Black 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 2bh â 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)).

# Red-Black 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 red-black tree.
• If the parent is red, need to fix the "double red" violation.
• We know the grandparent is black.

# Red-Black Trees - Insertion

• Four possible configurations given black grandparent:
• Smallest, middle, and largest labeled n1, n2, n3
• Their children are labeled in sorted order, starting with t1

• Figure 21 The Four Possible Configurations of a "Double Red"

# Red-Black Trees - Insertion Figure 22 Fix the "double-red" by rearranging the nodes

• Move up the tree fixing any other "double-red" 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

# Red-Black Trees - Insertion

• When the height of the binary search tree is h:
• Finding the insertion point takes at most h steps
• Fixing double-red violations takes at most h / 2
• Because we know h = O(log(n)), insertion is guaranteed O(log(n)) efficiency.

# Red-Black Trees - Removal

• Before removing a node in a red-black tree, turn it red and fix any double-black and double-red 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 • 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

# Red-Black 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 Negative-Red Node with a Double-Black Parent

# Red-Black Trees - Removal

• Fixing a Double-Red Violation Also Fixes a Double-Black Grandparent # Red-Black Trees - Removal Figure 25 Bubbling Up a Double-Black Node

• 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

# Red-Black 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 red-black 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 red-black trees that have four nodes?
• # Self Check 17.27

Why does Figure 21 show all possible configurations of a double-red 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 triple-red 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, n2 must have been the inserted node. Because the tree was a valid red-black tree before insertion, t1 couldn't have had a red root. Now consider the step after one double-red removal. The parent of n2 in Figure 22 may be red, but then n2 can't have a red siblingâotherwise the tree would not have been a red-black tree.

# Self Check 17.29

When removing an element, show that it is possible to have a triple-red 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 triple-red violation when the double-red 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 ti has a red root. However, all of them become children of the black n1 and n3 in Figure 22.

# Heaps

• A heap (min-heap) :
• 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 Figure 27A Heap

• The value of every node is smaller than all its descendants.

# Heaps

## Differences from a binary search tree

1. The shape of a heap is very regular.
• Binary search trees can have arbitrary shapes.
2. 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

1. Add a vacant slot to the end of the tree.
2. 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.
3. 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
1. Extract the root node value.
2. 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
3. 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 2h-1 and 2h nodes (n)
• 2h-1≤ n < 2h
• h â 1 ≤ log2(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 .

# Heaps

• A max-heap has the largest element stored in the root.
• A min-heap can be used to implement a priority queue.

# 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 almost-complete 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?  # 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 max-heap rather than a min-heap.

• # 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 max-heap!

# 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.