CIS 265 Homework 5 Implementing an Efficient Heapsort Algorithm
CIS 265 – Homework 5 – Implementing an Efficient HeapSort Algorithm
In this assignment you are asked to create a MaxHeapclass capable of holding generic comparable objects(the TYPE of elements to be inserted is <E extends Comparable<E>).
The class must expose three public methods:
- publicvoid add( E newItem )
- public E delete()
- publicvoid show()
Respectively, the methods (1) insert a new element in the heap, (2) remove the root of the heap, and (3) ‘nicely’ show the contents of the heap.
Test your application with the following two samples
Sample1:
int[] list = { 2, 9, 5, 4, 8, 1, 6, 7 };
Sample2:
GeometricObject[] list2 = {new Circle(2), new Circle(9), new Circle(5),
new Circle(4), new Circle(8), new Circle(1),
new Circle(6), new Circle(7),
new Rectangle(1,2) };
whereGeometricObject, Circle, and Rectangle are similar to the classes used in Homework2
In both cases begin with an empty MaxHeap, insert the items from each list, and finally remove one at the time, show this procedure could be used to sort generic data in ascending as well as descending order.
SOLUTION
packagecsu.matos;
importjava.util.ArrayList;
publicclass Driver3HeapSort {
/**
* Author:V. Matos
* Date:April-11, 2013
* Goal: Create a generic MAX-HEAP and use it to sort a collection of objects
*/
publicstaticvoid main(String[] args) {
// testing the MaxHeap with a list of Integer objects
int[] list = { 2, 9, 5, 4, 8, 1, 6, 7 };
// populate the heap
HeapSort<Integer> hs = newHeapSort<Integer>();
for (inti = 0; ilist.length; i++) {
hs.add(list[i]);
hs.show();
}
// remove root of the tree until empty
ArrayList<Integer> solution1 = newArrayList<Integer>();
for (inti = 0; ilist.length; i++) {
Integer item = hs.delete();
solution1.add(0,item);
System.out.println("\nRemoved " + item.toString() );
hs.show();
}
System.out.println( solution1 );
//sorting geometric figures
GeometricObject[] list2 = { new Circle(2), new Circle(9), new Circle(5),
new Circle(4), new Circle(8), new Circle(1),
new Circle(6), new Circle(7),
new Rectangle(1,2) };
HeapSortGeometricObject> hs2 = newHeapSortGeometricObject>();
// populate heap
for (inti = 0; i < list2.length; i++) {
hs2.add(list2[i]);
hs2.show();
}
// remove root from the heap
ArrayListGeometricObject> solution2 = newArrayListGeometricObject>();
for (int j = 0; j < list2.length; j++) {
GeometricObject item = hs2.delete();
solution2.add(0,item);
System.out.println("\nRemoved " + item.toString() );
hs2.show();
}
// show results
System.out.println("\n\n");
for (inti=0; i<solution2.size(); i++){
GeometricObject g = solution2.get(i);
System.out.printf ("\n%d \tArea:%4.2f \t %s", i, g.getArea(), g.getClass().toString() );
}
}
}//Driver
HEAP CLASS
packagecsu.matos;
importjava.util.ArrayList;
publicclass HeapSort <E extends Comparable<E> {
privateArrayList<E> a = newArrayList<E>();
publicvoid add( E newItem ){
a.add(newItem);
int son = a.size()-1;
while ( son > 0 ){
int dad = (son -1)/2;
E dadItem = a.get(dad);
E sonItem = a.get(son);
if ( dadItem.compareTo(sonItem) >= 0 ){
return;
}
E tempItem = dadItem;
a.set(dad, sonItem);
a.set(son, tempItem);
son = dad;
}
}//add
public E delete(){
int root = 0;
if (a.size() == 0)
returnnull;
if (a.size() == 1)
returna.remove(root);
int n = a.size()-1;
E deletedItem = a.get(root);
E lastItem = a.remove(n);
n--;
a.set(root, lastItem);
int left, right, max;
E tempItem;
while( 2*root+1 <= n ){
left = 2*root + 1;
right = 2*root + 2;
//the root has a left and right child
if (( left <= n ) & ( right <= n)) {
max = getLocMax(a, left, right);
if ( a.get(root).compareTo(a.get(max)) < 0 ){
tempItem = a.get(root);
a.set(root, a.get(max) );
a.set(max, tempItem);
root = max;
} else {
returndeletedItem;
}
}
//the root has left but not a right child
elseif (( left <= n ) & ( right > n)) {
max = getLocMax(a, left, root);
if ( a.get(root).compareTo(a.get(max)) < 0 ){
tempItem = a.get(root);
a.set(root, a.get(max) );
a.set(max, tempItem);
root = max;
} else {
returndeletedItem;
}
}
}//while
returndeletedItem;
}
/// ///////////////////////////////////////////////////////////////////////
privateintgetLocMax(ArrayList<E> a, int left, int right) {
if ( a.get(left).compareTo(a.get(right)) >= 0 )
return left;
else
return right;
}
publicvoid show(){
System.out.println();
for (inti=0; ia.size(); i++ ){
System.out.print(" " + a.get(i) );
}
}
}
RESULTS
2
9 2
9 2 5
9 4 5 2
9 8 5 2 4
9 8 5 2 4 1
9 8 6 2 4 1 5
9 8 6 7 4 1 5 2
Removed 9
8 7 6 2 4 1 5
Removed 8
7 5 6 2 4 1
Removed 7
6 5 1 2 4
Removed 6
5 4 1 2
Removed 5
4 2 1
Removed 4
2 1
Removed 2
1
Removed 1
[1, 2, 4, 5, 6, 7, 8, 9]
> Circle - white Radius:2.00 Area:12.57
> Circle - white Radius:9.00 Area:254.47
> Circle - white Radius:2.00 Area:12.57
> Circle - white Radius:9.00 Area:254.47
> Circle - white Radius:2.00 Area:12.57
> Circle - white Radius:5.00 Area:78.54
> Circle - white Radius:9.00 Area:254.47
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:5.00 Area:78.54
> Circle - white Radius:2.00 Area:12.57
> Circle - white Radius:9.00 Area:254.47
> Circle - white Radius:8.00 Area:201.06
> Circle - white Radius:5.00 Area:78.54
> Circle - white Radius:2.00 Area:12.57
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:9.00 Area:254.47
> Circle - white Radius:8.00 Area:201.06
> Circle - white Radius:5.00 Area:78.54
> Circle - white Radius:2.00 Area:12.57
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:1.00 Area:3.14
> Circle - white Radius:9.00 Area:254.47
> Circle - white Radius:8.00 Area:201.06
> Circle - white Radius:6.00 Area:113.10
> Circle - white Radius:2.00 Area:12.57
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:1.00 Area:3.14
> Circle - white Radius:5.00 Area:78.54
> Circle - white Radius:9.00 Area:254.47
> Circle - white Radius:8.00 Area:201.06
> Circle - white Radius:6.00 Area:113.10
> Circle - white Radius:7.00 Area:153.94
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:1.00 Area:3.14
> Circle - white Radius:5.00 Area:78.54
> Circle - white Radius:2.00 Area:12.57
> Circle - white Radius:9.00 Area:254.47
> Circle - white Radius:8.00 Area:201.06
> Circle - white Radius:6.00 Area:113.10
> Circle - white Radius:7.00 Area:153.94
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:1.00 Area:3.14
> Circle - white Radius:5.00 Area:78.54
> Circle - white Radius:2.00 Area:12.57
> Rectangle white
created: Wed Apr 10 20:11:22 EDT 2013 color: white filled: true
> Height: 2.0 Width: 1.0 Perimeter: 6.0 Area: 2.0
Removed
> Circle - white Radius:9.00 Area:254.47
> Circle - white Radius:8.00 Area:201.06
> Circle - white Radius:7.00 Area:153.94
> Circle - white Radius:6.00 Area:113.10
> Circle - white Radius:2.00 Area:12.57
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:1.00 Area:3.14
> Circle - white Radius:5.00 Area:78.54
> Rectangle white
created: Wed Apr 10 20:11:22 EDT 2013 color: white filled: true
> Height: 2.0 Width: 1.0 Perimeter: 6.0 Area: 2.0
Removed
> Circle - white Radius:8.00 Area:201.06
> Circle - white Radius:7.00 Area:153.94
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:6.00 Area:113.10
> Circle - white Radius:2.00 Area:12.57
> Rectangle white
created: Wed Apr 10 20:11:22 EDT 2013 color: white filled: true
> Height: 2.0 Width: 1.0 Perimeter: 6.0 Area: 2.0
> Circle - white Radius:1.00 Area:3.14
> Circle - white Radius:5.00 Area:78.54
Removed
> Circle - white Radius:7.00 Area:153.94
> Circle - white Radius:6.00 Area:113.10
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:5.00 Area:78.54
> Circle - white Radius:2.00 Area:12.57
> Rectangle white
created: Wed Apr 10 20:11:22 EDT 2013 color: white filled: true
> Height: 2.0 Width: 1.0 Perimeter: 6.0 Area: 2.0
> Circle - white Radius:1.00 Area:3.14
Removed
> Circle - white Radius:6.00 Area:113.10
> Circle - white Radius:5.00 Area:78.54
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:1.00 Area:3.14
> Circle - white Radius:2.00 Area:12.57
> Rectangle white
created: Wed Apr 10 20:11:22 EDT 2013 color: white filled: true
> Height: 2.0 Width: 1.0 Perimeter: 6.0 Area: 2.0
Removed
> Circle - white Radius:5.00 Area:78.54
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:2.00 Area:12.57
> Circle - white Radius:1.00 Area:3.14
> Rectangle white
created: Wed Apr 10 20:11:22 EDT 2013 color: white filled: true
> Height: 2.0 Width: 1.0 Perimeter: 6.0 Area: 2.0
Removed
> Circle - white Radius:4.00 Area:50.27
> Circle - white Radius:2.00 Area:12.57
> Rectangle white
created: Wed Apr 10 20:11:22 EDT 2013 color: white filled: true
> Height: 2.0 Width: 1.0 Perimeter: 6.0 Area: 2.0
> Circle - white Radius:1.00 Area:3.14
Removed
> Circle - white Radius:2.00 Area:12.57
> Circle - white Radius:1.00 Area:3.14
> Rectangle white
created: Wed Apr 10 20:11:22 EDT 2013 color: white filled: true
> Height: 2.0 Width: 1.0 Perimeter: 6.0 Area: 2.0
Removed
> Circle - white Radius:1.00 Area:3.14
> Rectangle white
created: Wed Apr 10 20:11:22 EDT 2013 color: white filled: true
> Height: 2.0 Width: 1.0 Perimeter: 6.0 Area: 2.0
Removed
> Rectangle white
created: Wed Apr 10 20:11:22 EDT 2013 color: white filled: true
> Height: 2.0 Width: 1.0 Perimeter: 6.0 Area: 2.0
0 Area:2.00 class csu.matos.Rectangle
1 Area:3.14 class csu.matos.Circle
2 Area:12.57 class csu.matos.Circle
3 Area:50.27 class csu.matos.Circle
4 Area:78.54 class csu.matos.Circle
5 Area:113.10 class csu.matos.Circle
6 Area:153.94 class csu.matos.Circle
7 Area:201.06 class csu.matos.Circle
8 Area:254.47 class csu.matos.Circle