May the 4th be with you.
Update: If you submit your BST without remove you will get full credit.
If you get remove to work correctly (on time), you will get extra credit.
Goal: One heaping helping of data structures.
Heaps are binary tree like structure
Restrictions when creating heaps:
Ex: max heap
a b c d
it would be filled starting from a to b to c then d
get max = O(1)
add/remove root = O(logn)
add - 1) put the value in the next open spot
2) push up the value
1) replace the root with the lower right node (bottom row rightmost node)
2) push it down into the correct place.
Note, the Next position: the lower right most empty spot.
Add a value:
1)The first add makes the value the root
2) puts the new value in the to the next position and checks if the new element is in the correct spot. If not, swap the value with the parent, (repeat) until you have a heap.
Using arrays for heaps
Our array can store the values of the heap like this:
1(Put the value here into index 1)
2 3(put the value here into index 3)
4 5 6 7
8 9 10 11 12 13 14 15
Notice there is no ‘0’ because doing it this way is much nicer. If we stored int then we could use index 0 as the size variable.
would become an array:
null a b c