Changes 1/21/15 - More EIMACS Binary Search Trees

I read more about binary search trees on EIMACS, like how they are sorted as the initial values are appended. It showed a little bit of the behavior of Java's TreeSet class, like the fact that #toString() uses an inorder traversal to output values. Then it started teaching me about heaps, which are structured like BSTs but with a different sorting method. There are two types: a min-heap and a max-heap. Min-heap means that the value at the root of each tree is less than the value of each of its branches, whereas a max-heap means that the root of each tree is greater than the values of each of its branches.

This is a min-heap: each node's value is greater than the value of its parent.

EIMACS really didn't to a good job of explaining complete trees, but I think that in order for a heap to behave correctly it needs to be complete.  This means that the nodes fill from left to right such that there is never a node with a right branch but not a left one, while also keeping greater or equal amounts of nodes on the left as compared to the right.

Heaps can also be represented as arrays, with each level being added successively.  EIMACS also inserts a null value at position zero to make some properties easier to describe.

The above heap would be written as {null, 1, 2, 3, 17, 19, 36, 7, 25, 100}, and would have the following properties:
The index of a given node's child elements will be at double that node's index and, if a right node exists, double that node's index + 1.
The inverse is also true: a given node's parent element can be found by taking (int)(node index / 2).

This seems like it is definitely useful!  EIMACS gives priority queues as an example where heapsorts are often used.

An algorithm that organizes nodes to create a min-heap does the following:
Each value is added as a new leaf to the bottom row or starts a new row if the current bottom is full. If the new value is found to be greater than or equal to the parent value, then the insertion is complete. Otherwise, the values of the new node and the parent node are swapped.