Notes on Heaps (1/16/15)

Today, I worked on learning about Heaps!

A heap, according to EIMACS, is a binary tree, whose values are Comparable objects. Also, a heap has to have met one of the following two properties:

1. Each node's value is greater than or equal to the parent. [Called the Min-Heap Property]
2. Each node's value is less than or equal to the parent. [Called the Max-Heap Property]

In heaps, the highest, or lowest, value of the entire tree is already at the root position. This allows for a lot of uses!

A good example of a Max-Heap is shown below:

"Max-Heap" by Ermishin - Own work. Licensed under CC BY-SA 3.0 via Wikimedia Commons - http://commons.wikimedia.org/wiki/File:Max-Heap.svg#mediaviewer/File:Max-Heap.svg

As shown above, heaps need to be complete. An example of an incomplete heap is shown below, courtesy of EIMACS:

For example, the right branch is not fully complete - there is no "F" value. Incomplete heaps can not exist.

There are other reasons as well as to why heaps would not be compatible, for example if they do not meet the Min-Heap or Max-Heap properties.

The following code example below, courtesy of EIMACS, allows for elements to be taken from an array and inserted into a Heap, one-by-one.

public static <T extends Comparable<T>> void heapInsert( ArrayList<T> heap, T value){
    int newValueIndex = heap.size();
    heap.add( newValueIndex, value );

    while ( newValueIndex > 1 ){
        int parentIndex = ( newValueIndex / 2 );
        T parentValue = heap.get( parentIndex );
        if ( value.compareTo( parentValue ) < 0 ){
            heap.set( parentIndex, value );
            heap.set( newValueIndex, parentValue );

            newValueIndex = parentIndex;
        }
        else {
            return;
        }
    }
}

There are many features as to why developers would like to use heaps. Obviously with heaps you are left with two options, as described above. You could go the Min-Heap route, where the smallest value is most easily accessible, or the Max-Heap route, where the largest value is most easily accessible. As a result, it is stated that heaps are often used for priority queues. Sorting is fast and efficient with heaps, completing in only O(nlog(n)) time. This mentioned algorithm is called HeapSort.

How do HeapSorts work? It's fairly simple.

1. All values are inserted one-by-one into a binary tree. It is made sure that this tree is a heap.
2. The root of this tree is removed, but a value takes it place such that it stays a heap.
3. This method is completed several times until all of the values have been checked.

With a time of only O(nlog(n)), it's just as good as a well-run quicksort or merge sort. As a result, it's often used by developers.

The three methods needed for a HeapSort are shown below:

public static <T extends Comparable<T>> void heapInsert( ArrayList<T> heap, T value ){
    int newValueIndex = heap.size();
    heap.add( newValueIndex, value );
    while ( newValueIndex > 1 ){
        int parentIndex = ( newValueIndex / 2 );
        T parentValue = heap.get( parentIndex );
        if ( value.compareTo( parentValue ) < 0 ){
            heap.set( parentIndex, value );
            heap.set( newValueIndex, parentValue );
            newValueIndex = parentIndex;
        }
        else {
            return;
        }
    }
}

public static <T extends Comparable<T>> T heapRemove( ArrayList<T> heap ){
    if ( heap.size() < 3 ){
        return heap.remove( 1 );
    }
    T root = heap.get( 1 );
    T lastValue = heap.remove( heap.size() - 1 );
    int valueIndex = 1;
    heap.set( valueIndex, lastValue );
    int childIndex = ( 2 * valueIndex );
    while ( childIndex < heap.size() ){
        T childValue = heap.get( childIndex );
        if ( childIndex + 1 < heap.size() && childValue.compareTo(heap.get( childIndex + 1 )) > 0 ){
            childIndex++;
            childValue = heap.get( childIndex );
        }
        if ( lastValue.compareTo( childValue ) > 0 ){
            heap.set( childIndex, lastValue );
            heap.set( valueIndex, childValue );
            valueIndex = childIndex;
        }
        else {
            return root;
        }
    }
    return root;
}

public static <T extends Comparable<T>> void heapSort( ArrayList<T> a ){
    ArrayList<T> heap = new ArrayList<T>();
    heap.add( null );
    for ( int i = 0 ; i < a.size(); i++ ){
        heapInsert( heap, a.get( i ) );
    }
    for ( int i = 0 ; i < a.size(); i++ ){
        a.set( i, heapRemove( heap ) );
    }
}

Once these methods are in your class, you can simply call them from your main method and use HeapSorts!

Notes on Binary Search Trees (1/15/15)

Today I worked on Binary Search Trees.

Binary Search Trees, according to EIMACS, are binary trees whose values are instances of reference types - they implement the Comparable<T> interface. They can never have the same value more than once.

In a Binary Search Tree, each left value is less than the root value, and each right value is greater than the root value. A good picture example of this is this, also from EIMACS:

A perfect example as to why a developer would choose a Binary Search Tree is that it has a very efficient search algorithm, as seen below. This method will return a the TreeNode where the defined value exists, and otherwise, return null. As a result of the compareTo method and the Comparable interface, it is much quicker and efficient than other methods.

static TreeNode searchBST( TreeNode tree, Comparable value )
{
    if ( tree == null ){
        return null;

    }
    Object rootVal = tree.getValue();
    if ( value.equals( rootVal ) ){
        return tree;

    }
    if ( value.compareTo( rootVal ) < 0 ){
        return searchBST( tree.getLeft(), value );

    }
    else
}

As previously stated, this method has a great deal of use if you're working with trees. Granted that your Binary Tree is pre-sorted, this method will allow for fast accessing of data - a perfect reason to use a Binary Tree.

Creating Binary Search Trees isn't all too difficult, as shown in EIMACS, the buildBST and insertLeaf methods, as shown below, can both create and insert data into a Binary Search Tree.

public static TreeNode buildBST( ArrayList<Comparable> values )
{
    TreeNode newTree = null;
    for ( int i = 0 ; i < values.size() ; i++ ){
        newTree = insertLeaf( newTree, values.get( i ) ); 

    }
    return newTree;
}


public static TreeNode insertLeaf( TreeNode tree, Comparable value )
{
    if ( tree == null ){
        return new TreeNode( value );

    }

    if ( value.compareTo( tree.getValue() ) < 0 ){
        tree.setLeft( insertLeaf( tree.getLeft(), value ) );
    }
    else {
        tree.setRight( insertLeaf( tree.getRight(), value ) );
    }
    return tree;
}

Additionally noted in this section is the TreeSet<E> interface. All objects in this must be Comparable<E> objects. It also allows for quick searching, adding, and removing of objects, none of which take more than O(log(n)) time.

TreeMap<K, V> is also a noted interface. All objects in this must be Comparable<K> objects, and the methods available for this interface are get, put, containsKey, and remove. They also can be completed in O(log(n)) time or less, and objects in the TreeMap are stored and retrievable in the same order, which is advantageous in certain situations.

I also began to install Xcode, which apparently can be used for Java. I wanted to experiment with it a bit later on when I go back to Android development, and since I've heard it's a fairly decent IDE, I thought it would be worth a try. It only took two or so minutes, so I didn't lose too much time by doing this either!

Tomorrow I will add information on Heaps!

Notes on Binary Traversals (1/14/15)

Today I worked on Binary Traversals and took some notes on them. Basically, there are 7 types of traversals:

Preorder Traversal - Looks at the root value, then the left subtree, then the right subtree.
Reverse Preorder Traversal - Also looks at the root value, then the right subtree, then the left subtree.
Inorder Traversal - Looks at the left subtree, then the root, then the right subtree.
Reverse Inorder Traversal - Looks at the right subtree, then the root, then the left subtree.
Postorder Traversal - Looks at the left subtree, then the right subtree, then the root.
Reverse Postorder Traversal - Looks at the right subtree, then the left subtree, then the root.
Level-by-level Traversal - Looks at all the nodes, level by level, going down one at a time, from left to right.

As can be seen, there are many different ways to traverse Binary Trees. I've added the following example below to look at a Preorder Traversal (taken from EIMACS):

public void printValues(TreeNode tree){
    System.out.print( tree.getValue() );
    if ( tree.getLeft() != null ){
        printValues( tree.getLeft() );
    }
    if (tree.getRight() != null ){
        printValues( tree.getRight() );

    }

}

Although this is more of a simplistic example, you can see that all other types of traversals would be similar to this. For example, a reverse preorder traversal would be the following:

public void printValuesReverse(TreeNode tree){
    System.out.print( tree.getValue() );
    if (tree.getRight() != null ){
        printValuesReverse( tree.getRight() );

    }

    if ( tree.getLeft() != null ){
        printValuesReverse( tree.getLeft() );
    }

}

This can be done for all types of binary tree traversals. Although it is a simplistic concept, it outlines important ways of finding your data via binary trees. Each type of traversal has its own advantages and disadvantages, and is left to the developer to figure out which would be the best method to choose.

Examples and Notes on Trees

A tree, continuing on from linked lists, is a data structure used in Java. It starts with the initial node, called the root, and then contains several nodes that may contain references to many other nodes. The initial nodes are considered roots of subtrees. It is described on Wikipedia here, however this description isn't entirely Java-based, rather just of the general programming concept of Trees. A good example of a tree would be the image below:

20 would be the root, or initial node, and number 15 would be the left node and 30 would be the right node. This has the ability to continue as long as the developer would like, and allows for quick sorting and accessing of data.

A good example of a tree can be seen from the example below, taken from EIMACS:

public class TreeNode
{
private Object value;
private TreeNode left;
private TreeNode right;
public TreeNode( Object initValue )
{
value = initValue;
left = null;
right = null;
}
public TreeNode( Object initValue,
TreeNode initLeft,
TreeNode initRight )
{
value = initValue;
left = initLeft;
right = initRight;
}
public Object getValue() { return value; }
public TreeNode getLeft() { return left; }
public TreeNode getRight() { return right; }
public void setValue( Object newValue )
{
value = newValue;
}
public void setLeft( TreeNode newLeft )
{
left = newLeft;
}
public void setRight( TreeNode newRight )
{
right = newRight;
}
}
As seen, this class allows for tree nodes to be modified and created. If used properly, it will allow for the full creation of a binary tree!

The setLeft and setRight methods allow for creation of the left and right children, respectively. setValue allows for a certain value to be reset, and getValue is a getter method to find a certain value. Although it's a bit more complex than the previously explained searching and sorting methods, once you understand it, you'll have a much better way to set, sort, and access data.

1/9/15

Today I took Test 23 and got everything right!

I also began working on the Trees section. It looks a bit complex, so I will start taking notes on here starting Monday.

1/7/15-1/8/15

On Wednesday (1/17) I started working on a UMD problem, #5. I haven't fully completed it but I'll continue working on it.

Today I studied a bit more for Test 23. I'm ready to take it tomorrow as long as the class time is normal again!

1/5/15

Today I mainly worked on studying Sets and Maps. I worked on some of the exercises as well. I finished the chapter completely, so I'm ready to take the test on them tomorrow!