Errata

Using a heap with the smallest element at the top, we can keep track of the
largest k elements. Let’s analyze the performance of this algorithm. For each
element, we perform one of:

• Branch 1: Adding an element to the heap is O(log k).

• Branch 2: Finding the smallest element in the heap is O(1).

• Branch 3: Removing the smallest element is O(log k). Adding x is also
O(log k).

Should be rewritten as:

Let’s analyze the performance of this algorithm. For each element, we
perform one, two, or all of these operations:

• Finding the smallest element in the heap, which is O(1).

• Removing the smallest element, which is O(log k).

• Adding an element to the heap, which is O(log k).

My implementation of a linked list, MyLinkedList, uses a singly linked
list; that is, each element contains a link to the next, and the
MyArrayList object
itself has a link to the first node.

Should be “MyLinkedList”

In this example, it takes nine comparisons to find the target, even though
the tree contains nine keys. In general, the number of comparisons is
proportional to the height of the tree, not the number of keys in the tree.

Should be 4

There’s not much to it; an Entry is just a container for a key and a value.
This definition is nested inside MyLinearList, so it uses the same type
parameters, K and V.

Should be "MyLinearMap"