CS 61B

Time: Sat 10/27/17 2 pm (moved from Tue 10/24/17 10 am)

Trees onto Heap & Priority Queues

Property of a min/max heap? Is it easier to find a min or a max item in a min heap? What'll be the best/worst height of a heap (if drawn like a tree) for n nodes? What are the procedures of adding an item to a tree or of removing an item from a tree? (The entry removal is a little more difficult.)

What's the result tree after removing the minimum from the following min heap [0, 1, 4, 8, 2, 6, 8, 9]?

A heap can be stored in an array--begin with index 0 or index 1?

Additionally, if possible, how can we use a min heap to implement a max heap?


Assume integers are represented by 32 bits. If they are unsigned, how many distinct integers can be stored?

Think of a way to represent negative numbers. Does storing a sign bit by itself efficient when going into computation--4 different cases of adding numbers, whoa?! What's the number of distinct integers (signed) this can represent?

Check out two's complement--is this option a little bit easier, or not? Is the heavy math computation easier less troublesome without the various 4 cases? What's the range now? What's the min/max integer in two's complement, written in hexadecimal?

How do we negate an integer in two's complement?

There's a weird number within the range that the integer itself is its own negation.

Common bitwise operations: &, |, ~, ^, <<, >> and >>>.


There's quite a close relationship between Object.equals() and Object.hashCode(). What's a perfect hashing?

In a best/worst scenario, what's the runtime of inserting/finding an element in a hash set (with external linked list)?

Can this improved by tying to another data structure other than linked list?


Why do we care using generics? What's a generic type parameter?

Generics have to be around classes; after all (pretty much) everything is just an object, like literally, with type erasure.


  1. Will the following class compile?

    public final class Algorithm {
      public static <T> T max(T x, T y) {
        return x > y ? x : y;
  2. Write a generic method to exchange the positions of two different elements in an array.

    public final class Algorithm {
      public static <T> void swap(T[] a, int i, int j) {
        /* Code here */
  3. Will the following code compile?

    public static void print(List<? extends Number> list) {
      for (Number n : list)
        System.out.print(n + " ");
  4. Given the following classes:

    class Shape { /* ... */ }
    class Circle extends Shape { /* ... */ }
    class Rectangle extends Shape { /* ... */ }
    class Node<T> { /* ... */ }

    Will the following code compile? If not, why?

    Node<Circle> nc = new Node<>();
    Node<Shape> ns = nc;

Questions selected from The Java™ Tutorials: Questions and Exercises: Generics.