Binary Heap in Java

I’ve found code for making a binary heap based off an array list. It seemed like a neat way to code for a simple heap but I would still preferred to stick with binary trees.  Anyway, I stumbled upon this link while browsing the binary heap wikipedia page.

http://en.wikipedia.org/wiki/Binary_heap

https://sites.google.com/site/indy256/algo-en/binary_heap

Besides simple syntax changes, the only real change I did was with the print method. The original implantation popped each element off the heap which didn’t seem like a good idea to me. I just made a simple iterator to print each element to standard out. If the T’s look confusing to you read about generics in Java. Here is something to get you started.
http://docs.oracle.com/javase/tutorial/java/generics/gentypes.html

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class BinaryHeap<T extends Comparable<T>> {
	List<T> heap = new ArrayList<T>();

	public BinaryHeap(){}

	public BinaryHeap( T[] keys ){
		for ( T key : keys)
			this.heap.add(key);
		for ( int pos = ( this.heap.size() / 2 - 1 ); pos >=0; pos-- )
			this.moveDown(pos);
	}

	public void add(T node){
		this.heap.add(node);
		this.moveUp(this.heap.size() -1 );
	}

	public void moveUp(int pos){
		while (pos > 0){
			int parent = ( pos -1 ) / 2;

			if ( this.heap.get(pos).compareTo(this.heap.get(parent)) >= 0)
				break;

			Collections.swap(this.heap, pos, parent);
			pos = parent;
		}
	}

	public void moveDown(int pos){
		while ( pos < ( this.heap.size() / 2 ) ){
			int child = 2 * pos + 1;
			if ( ( child < ( this.heap.size() - 1 ) ) &&
				( this.heap.get(child).compareTo( this.heap.get(child + 1) ) <= 0 ) )
				++child;

			if ( this.heap.get(pos).compareTo(this.heap.get(child)) <= 0 )
				break;

			Collections.swap(this.heap, pos, child);
			pos = child;
		}
	}

	public T remove(){
		T removeNode = this.heap.get(0);
		T tailNode = this.heap.remove(this.heap.size() - 1 );

		if (!this.heap.isEmpty() ){
			this.heap.set(0, tailNode);
			this.moveDown(0);
		}

		return removeNode;
	}

	public void print(){
		for( Iterator<T> iter = this.heap.iterator(); iter.hasNext(); )
			System.out.println(iter.next() );
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s