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!