0 Replies - 382 Views - Last Post: 22 February 2010 - 01:02 PM

#1 toshiro   User is offline

  • D.I.C Head
  • member icon

Reputation: 21
  • View blog
  • Posts: 137
  • Joined: 27-June 09

Data Structure: Heap

Posted 22 February 2010 - 01:02 PM

Description: Heaps are data structures that effectivly act like Binary Search Trees within an array, cutting down on the overhead of having pointers and nodes.
import java.util.ArrayList;

public class Heap extends ArrayList
{
	private int child1, child2;

	// instance field
	public Heap()
	{
		child1 = 0;
		child2 = 0;
	}
	/**
	 * add the the end of the array and bubble down the array while the parent of the child is greater and the child's index!= 1
	 * @param data
	 */
	public void addItem(int data)
	{
		this.add(data);
		int index = size()-1;
		int parent = (index - 1) / 2;
		while (index != 0 && this.compareTo((Integer) this.get(parent), (Integer) this.get(index)) == 1)
		{
			Integer temp = (Integer) this.get(parent);				
			Integer child = (Integer) this.get(index);
			this.set(index, temp);
			this.set(parent, child);
			index = parent;
			parent = (index - 1) / 2;
		}
	}

	/**
	 * remove root by replacing with the last item while(item has children and
	 * item is larger then either of its children) swap item with its smaller
	 * child, moving item down the heap
	 * 
	 * @param data
	 */
	public int removeItem()
	{
		if (isEmpty())
		{
			System.err.println("empty heap");
			throw new IllegalArgumentException();
		}
		int LIH = 0;
		Integer IBR = (Integer) get(0);
		set(0, get(size()-1));
		remove(size() - 1);
		if (!isEmpty())
		{
			if (2 * LIH + 1 < this.size())
			{
				child1 = this.compareTo((Integer) this.get(LIH), (Integer) this.get(2 * LIH + 1));
			}
			if (2 * LIH + 2 < this.size())
			{
				child2 = this.compareTo((Integer) this.get(LIH), (Integer) this.get(2 * LIH + 2));
			}
			while ((hasChildren(LIH) && child1 == 1) || (hasChildren(LIH) && child2 == 1))
			{
				//get children of LIH
				//swap LIH with smallest child
				//delegate one child to accept <= values
				//update LIH with old index (2x+1 or 2x+2)
				Integer left = null;
				Integer right = null;
				int childIndex = 0;
				if(2*LIH+1 < size() && child1 == 1)
					left = (Integer) get(2*LIH+1);
				if(2*LIH+2 < size() && child2 == 1)
					right = (Integer) get(2*LIH+2);
				if(left != null && right != null)
				{
					if(left <= right)
					{
						set(2*LIH+1, get(LIH));
						set(LIH, left);
						childIndex = 2*LIH+1;
					}
					else if(right < left)
					{
						set(2*LIH+2, get(LIH));
						set(LIH, right);
						childIndex = 2*LIH+2;
					}
				}
				else if(left != null)
				{
					set(2*LIH+1, get(LIH));
					set(LIH, left);
					childIndex = 2*LIH+1;
				}
				else if(right != null)
				{
					set(2*LIH+2, get(LIH));
					set(LIH, right);
					childIndex = 2*LIH+2;
				}
				LIH = childIndex;
				if (2 * LIH + 1 < this.size())
				{
					child1 = this.compareTo((Integer) this.get(LIH), (Integer) this.get(2 * LIH + 1));
				}
				if (2 * LIH + 2 < this.size())
				{
					child2 = this.compareTo((Integer) this.get(LIH), (Integer) this.get(2 * LIH + 2));
				}
					
			}
		}
		return (int) IBR;
	}

	public boolean hasChildren(int index)
	{
		return 2 * index + 1 < this.size() || 2 * index + 2 < this.size();
	}

	public int compareTo(int a, int b)
	{
		if (a < b)
			return -1;
		else if (a > b)
			return 1;
		else
			return 0;
	}
}


Is This A Good Question/Topic? 0
  • +

Page 1 of 1