//*****************************************************************//
//***********Random Reality Check - February 22nd, 2017***********//
//***************************************************************//

HEAPS REALITY CHECK (cont.) (Oh Joy!)
7) Big-O of deleting the min value from a heap?
Me: O(log n)
Them: Same! Have to re-heapify the tree after removal

8) Write the instance method "add" for a min-heap implementation that uses an array (assuming we start at 1); assume the array only holds ints; if the array is full, throw an unchecked exception:

public class minHeap {
    int size;
    int[] arr;
    minHeap() {arr = new int[100];}

    public void add(int value) {
        if (size == arr.length - 1) {
            throw new ArrayIndexOutOfBounds("heap is full");
        }
        size++;
        arr[size] = value;

        int current = size;
        while (current > 1 && arr[current / 2] > value) { //basic up-heapify
            arr[current] = arr[current / 2];
            arr[current / 2] = value;
            current /= 2;
        }
    }
}

HASHING REALITY CHECK (FURTHER JOY *__*)
FIRST: If you need help w/ hash maps, read chapter 10 in the book. Chapter 10 is great.
    -Assume hashcode() just returns the int passed in
    -Compression function = hashcode() % tableSize
    -tableSize = 7
    -DEL = delete marker

1) External chaining: add (8, 1, 15, 5, 2) to the list, then remove 8 and calculate the load factor
ME:  Final List: [{1, DEL, 15}, {2}, {5}]
    Load factor: 4.0 / 7

2) Linear probing: add (8, 1, 15, 5, 2), then remove 15

3) Quadratic Probing: add (8, 1, 15, 5, 2), remove 15, then search for 22 and calculate LF
CLASS SOLUTION: [null, 8, 1, 2, null, DEL, 5]
    -For adding, index = (hashCode() + h^2) % length; h starts at 0, goes up by 1 until we find an open spot
    -Removing 15 checks indices 1, 2, 5 (then removes it)
    -Searching for 22 will search indices 1, 2, 5, 3, 3, 5, 2
        -At this point, we've searched 7 times - aka, the length of the array - so we'll terminate at this point and assume 22 is not in the list
    -Load factor = 4.0 / 7