HotDogs

Team HotDogs -- Tim Marder, Maxwell Vale, Max Millar

ArrayPriorityQueue Methods

void add (String val)

Runtime: O(1)

Our Decision: We chose to use the built-in ArrayList add() for this method since it requires the least amount of work and has the fastest possible runtime (constant).

boolean isEmpty()

Runtime: O(1)

Our Decision: We chose to use the built-in ArrayList size() for this method to check if the length of the queue is equal to zero. It was a minimal amount of work and has the fastest possible runtime (constant).

String peekMin()

Runtime: O(n)

Our Decision: We created a variable that is the first element of the queue. We then used a foreach loop to traverse the elements and compare the current element to zero. If the element is larger than zero, then the variable was set to the element. According to the duke API for ArrayPriorityQueue, the average runtime for peekMin() is linear, which is what we achieved here. The variable with the final value is returned in the end.

String removeMin()

Runtime: O(n)

Our Decision: We used the previous method peekMin() to find the index of the smallest value in the queue. We then used the built-in ArrayList remove() method to remove that value from the queue. It was a minimal amount of work and achieved the average runtime (linear) as stated on the Duke API for ArrayPriorityQueue.

ALHeap

Prioritized Method List

1. isEmpty()
2. add(Integer addVal)
3. toString() --> The simple version
4. peekMin()
5. minChildPos(int pos)
6. removeMin()
7. toString() --> More Complicated Version

Method Algorithms

isEmpty()

Since the underlying ArrayList contained already has an isEmpty() method, we can simply use that method.

add(Integer addVal)

1. Add addVal to the end of the ArrayList (last element in bottom level of tree, left justified)
2. Compare the value of addVal to its current parent
   1. If addVal > parentVal, then addVal is in a valid position and min heap-ness is maintained
   2. If addVal < parentVal, swap addVal and parentVal.
3. Repeat the swapping until addVal is greater than its parent or it reaches the root, in which case addVal would be in a valid position in the min Heap (Heap-ness maintained!)

toString() --> Simple Version

Since the simple version is just to print the level-order traversal, you can simply print each element in the ArrayList with a space in between.

peekMin()

Since the Heap is a min Heap, the smaller value is always the parent of larger values. So, the smallest value of the min Heap would have to be at the root of the tree, which is first in a level-order traversal. That means that the smallest value should always be the first element in the ArrayList, so heap.get(0) should give the smallest value.

minChildPos(int pos)

1. If pos is out of bounds of the ArrayList size or if there are no children from pos (by checking if supposed children's indices are out of bounds of the ArrayList size), return -1
2. If there is only one child (the left child), you can return the index of that child (2 * pos + 1)
3. If there are two children, return the index of the smaller child

removeMin()

1. Swap the root of the tree with the rightmost element on the bottom level
2. Remove the last element in the ArrayList (should be where the smallest element was moved to)
3. Now, to maintain min Heap-ness, need to move the root value down the tree if necessary
4. If any of the root's children are smaller than the root itself, swap the root and the smaller child
5. Continue to swap until the value is smaller than both children

toString() --> More Complicated

Create instance variables to hold index and the final index of the next level in the tree. In order to keep track of the final index in the next level, the variable is incremented by an increasing power of two(1,2,4,8,etc.). For each element in the ArrayList, add the element to the return String. If the element's index is equal to the final index in that level, add "\n" to the return String and update the final index for the next level. Still haven't figured out how to get the branch ASCII to work.