Lab Goal : This lab was designed to teach you more about a heap.

Lab Description : Write a heap program. A heap is a binary tree structure implemented with an array. The root is a spot 0 and the roots children would be a spots 1 and 2. To find any indexes children, you use i*2+1 and i*2+2.

What does add do?

Add adds a new item in the very last spot in the tree(array spot length-1). Add then calls swapUp to restructure the tree so that the new item is in the proper location in the heap. swapUp first checks to see if the new item is bigger than its parent. If it is, swapUp swaps the parent and the new item and repeats the same process until the new item is in the root position or it finds that the new item is not larger than its current parent.

What does remove do?

Remove copies the root to a variable and then moves the last value in the tree to the root-array spot 0. Remove then calls swapDown to restructure the tree and to check that the tree remains a heap. swapDown looks at the children of the new root and determines which is larger. The larger of the children and the new root are then swapped. This process continues until the bottom of the tree is reached or there are no children larger than the current parent.

//(c) A+ Computer Science //www.apluscompsci.com //Name - import java.util.List; import java.util.ArrayList; import static java.lang.System.*; public class Heap { private List list; public Heap() { list = new ArrayList(); } public void add(int value) { list.add(value); swapUp(list.size()-1); } public void swapUp(int bot) { } public void remove( ) { list.set(0,list.get(list.size()-1)); list.remove(list.size()-1); swapDown(list.size()); } public void swapDown(int top) { } private void swap(int start, int finish) { } public void print() { out.println(" PRINTING THE HEAP! "); out.println(); } public String toString() { return list.toString(); } }

//(c) A+ Computer Science //www.apluscompsci.com //Name - import java.util.ArrayList; import static java.lang.System.*; public class HeapRunner { public static void main (String[] args) { Heap heap = new Heap(); heap.add(1); heap.add(2); heap.add(8); heap.add(9); heap.add(10); heap.add(7); heap.add(75); heap.add(17); heap.add(5); heap.print(); heap.remove(); heap.print(); heap.remove(); heap.print(); heap.remove(); heap.print(); heap.remove(); heap.print(); heap.remove(); heap.print(); heap.remove(); heap.print(); heap.remove(); heap.print(); heap.add(25); heap.print(); heap.add(35); heap.print(); heap.remove(); heap.print(); } }

A+ Computer Science HEAP BASICS Lab Goal: This lab was designed to teach you more about a heap. Lab Description : Write a heap program. A heap is a binary tree structure implemented with an array. The root is a spot 0 and the root's children would be a spots 1 and 2. To find any indexes children, you use 1+2+1 and i*2+2. What does add do? Add adds a new item in the very last spot in the tree array spot length-1). Add then calls swapUp to restructure the tree so that the new item is in the proper location in the heap swap Up first checks to see if the new item is bigger than its parent. If it is, swapUp swaps the parent and the new item and repeats the same process until the new item is in the root position or it finds that the new item is not larger than its current parent. What does remove do? Remove copies the root to a variable and then moves the last value in the tree to the root-array spot 0. Remove then calls swapDown to restructure the tree and to check that the tree remains a heap. swapDown looks at the children of the new root and determines which is larger. The larger of the children and the new root are then swapped. This process continues until the bottom of the tree is reached or there are no children larger than the current parent. Sample Output: PRINTING THE HEAP! Files Needed :: Heap.java HeapRunner.java 75 17 10 1 5 PRINTING THE HEAP! 17 9 10 5 B 2 7 1 PRINTING THE HEAP! 10 5 B 2 1 PRINTING THE HEAP! 9