Warm-Up Sequence

[darwinrlo]

Heaps

Min-Heaps

• Create a min-heap.
• Insert a key into a min-heap.
• Extract the minimum node of a min-heap. Give the running time.
• Delete an interior node of the min-heap. Give the running time.
• Heapify an existing list. Give the running time.
• Create a min-heap in which the values are different from the keys.
• Check to see if a min-heap is empty.
• Look up the minimum element of a min-heap without extracting it.

Max-Heaps

• Create a max-heap.
• Insert a key into a min-heap.
• Extract a key from a min-heap.

Patterns

• Use two heaps facilitate to facilitate computing the running median of a stream of numbers.
  • When should you insert a new number into the first heap? Into the second?
  • How are the heaps kept (about) the same size?

Solutions

[darwinrlo]

Python

• Use a format string.
• Delete the last element of a list.
• Concatenate a number to a string and print it.

[darwinrlo]

In Python, // is the operator for "floor division." 3 // 2 = 1. Note that -3 // 2 = -2 -- -2 is smaller than -1.

[darwinrlo]

Binary Search

A good implementation would set start to the index of the first element of the segment and end to the index of the last element. When the segment is simply the entire array, start is 0 and end is arr.length - 1. If the middle element is not equal to the target element and start equals end, then return -1.

If the order of the sort is not known, then compare the first element with the last element. For example, if the first element is less than the final element, then it is sorted in ascending order. The sort order determines which segment to recurse on if the middle element is not a match.

end - start gives the number of elements between the start of the last element and the start of the first element. Note that the last element is not included in this count.

• The total number of elements is end - start + 1.
• If end - start is even, then the total number of elements is odd. If end - start is odd, then the total number of elements is even.

If start and end are both odd or both even, then their difference is even. If one is odd while the other is even, their difference is even.

If there are even number of elements, then the midpoint is between the two middle elements. The floor or ceiling of (start + end)/2 will need to be taken to choose one of the two middle keys. If there are an odd number of elements, then there is a single element in the middle and neither the floor nor ceiling will need to be taken.

In Java, it is tempting to use (start + end)/2. But if start and end are very large, the numerator could overflow. It is better to use start + (end - start)/2. (The floor is implicitly taken here.) This makes the numerators involved smaller and less likely to overflow. In Python, there is no integer overflow so (start + end)/2 works just fine.

[darwinrlo]

If the input binary tree is not stipulated to be balanced, then in the worst case, it could be a linked list, meaning the tree would have height n. This confers DFS a worst-case running time of O(n) and space complexity of O(n).