Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit633d173

Browse files
author
jsquared21
committed
Add Ex 23.5
1 parent0cda939 commit633d173

17 files changed

+641
-0
lines changed
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
/*********************************************************************************
2+
* (Generic heap sort) Write the following two generic methods using heap sort. *
3+
* The first method sorts the elements using the Comparable interface and the *
4+
* second uses the Comparator interface. *
5+
* *
6+
* public static <E extends Comparable<E>> *
7+
* void heapSort(E[] list) *
8+
* public static <E> void heapSort(E[] list, *
9+
* Comparator<? super E> comparator) *
10+
*********************************************************************************/
11+
import java.util.Comparator;
12+
13+
public class Exercise_23_05 {
14+
15+
public static <E extends Comparable<E>> void heapSort(E[] list) {
16+
// Create a Heap
17+
Heap<E> heap = new Heap<>();
18+
19+
// Add elements to the heap
20+
for (int i = 0; i < list.length; i++)
21+
heap.add(list[i]);
22+
23+
// Remove elements form the heap
24+
for (int i = list.length - 1; i >= 0; i--)
25+
list[i] = heap.remove();
26+
}
27+
28+
public static <E> void heapSort(E[] list, Comparator<? super E> comparator) {
29+
// Create a Heap
30+
Heap<E> heap = new Heap<>(comparator);
31+
32+
// Add elements to the heap
33+
for (int i = 0; i < list.length; i++)
34+
heap.add(list[i], comparator);
35+
36+
// Remove elements from the heap
37+
for (int i = list.length - 1; i >= 0; i--)
38+
list[i] = heap.remove(comparator);
39+
}
40+
41+
/** A test method */
42+
public static void main(String[] args) {
43+
Integer[] intArray = {-44, -5, -3, 3, 3, 1, -4, 0, 1, 2, 4, 5, 53};
44+
heapSort(intArray);
45+
for (int i = 0; i < intArray.length; i++)
46+
System.out.print(intArray[i] + " ");
47+
48+
// Create an array of 10 GeometricObjects
49+
GeometricObject[] list = {new Circle(5), new Rectangle(4, 5),
50+
new Circle(5.5), new Rectangle(2.4, 5), new Circle(0.5),
51+
new Rectangle(4, 65), new Circle(4.5), new Rectangle(4.4, 1),
52+
new Circle(6.5), new Rectangle(4, 5)};
53+
heapSort(list, new GeometricObjectComparator());
54+
System.out.print("Sorted elements: ");
55+
for (GeometricObject e: list) {
56+
System.out.printf("%.2f ", e.getArea());
57+
}
58+
System.out.println();
59+
}
60+
}
Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
/*********************************************************************************
2+
* (Generic heap sort) Write the following two generic methods using heap sort. *
3+
* The first method sorts the elements using the Comparable interface and the *
4+
* second uses the Comparator interface. *
5+
* *
6+
* public static <E extends Comparable<E>> *
7+
* void heapSort(E[] list) *
8+
* public static <E> void heapSort(E[] list, *
9+
* Comparator<? super E> comparator) *
10+
*********************************************************************************/
11+
public class Exercise_23_05 {
12+
13+
}
Lines changed: 144 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,144 @@
1+
import java.util.Comparator;
2+
import java.util.ArrayList;
3+
4+
public class Heap <E extends Comparable<E>> {
5+
//public class Heap <E> {
6+
private Comparator<? super E> comparator;
7+
8+
private ArrayList<E> list;
9+
10+
11+
/** Create a default heap */
12+
public Heap() {
13+
list = new ArrayList<>();
14+
}
15+
16+
/** Creatre a heap from an array of objects */
17+
public Heap(Comparator<? super E> comparator) {
18+
this.comparator = comparator;
19+
list = new ArrayList<>();
20+
}
21+
22+
/** Add a new object into the heap */
23+
public void add(E newObject) {
24+
list.add(newObject); // Append to the heap
25+
int currentIndex = list.size() - 1; // The index of the last node
26+
27+
while (currentIndex > 0) {
28+
int parentIndex = (currentIndex - 1) / 2;
29+
// Swap if the current object is greater than its parent
30+
if (list.get(currentIndex).compareTo(
31+
list.get(parentIndex)) > 0) {
32+
E temp = list.get(currentIndex);
33+
list.set(currentIndex, list.get(parentIndex));
34+
list.set(parentIndex, temp);
35+
}
36+
else
37+
break; // The tree is a heap now
38+
39+
currentIndex = parentIndex;
40+
}
41+
}
42+
43+
/** Add a new object into the heap */
44+
public void add(E newObject, Comparator<? super E> comparator) {
45+
list.add(newObject); // Append to the heap
46+
int currentIndex = list.size() - 1; // The index of the last node
47+
48+
while (currentIndex > 0) {
49+
int parentIndex = (currentIndex - 1) / 2;
50+
// Swap if the current object is greater than its parent
51+
if (comparator.compare(list.get(currentIndex),
52+
list.get(parentIndex)) > 0) {
53+
E temp = list.get(currentIndex);
54+
list.set(currentIndex, list.get(parentIndex));
55+
list.set(parentIndex, temp);
56+
}
57+
else
58+
break; // The tree is a heap now
59+
60+
currentIndex = parentIndex;
61+
}
62+
}
63+
64+
/** Remove the root from the heap */
65+
public E remove() {
66+
if (list.size() == 0) return null;
67+
68+
E removedObject = list.get(0);
69+
list.set(0, list.get(list.size() - 1));
70+
list.remove(list.size() - 1);
71+
72+
int currentIndex = 0;
73+
while (currentIndex < list.size()) {
74+
int leftChildIndex = 2 * currentIndex + 1;
75+
int rightChildIndex = 2 * currentIndex + 2;
76+
77+
// Find the maximum between two children
78+
if (leftChildIndex >= list.size()) break; // The tree is a heap
79+
int maxIndex = leftChildIndex;
80+
if (rightChildIndex < list.size()) {
81+
if (list.get(maxIndex).compareTo(
82+
list.get(rightChildIndex)) < 0) {
83+
maxIndex = rightChildIndex;
84+
}
85+
}
86+
87+
// Swap if the current node is less than the maximum
88+
if (list.get(currentIndex).compareTo(
89+
list.get(maxIndex)) < 0) {
90+
E temp = list.get(maxIndex);
91+
list.set(maxIndex, list.get(currentIndex));
92+
list.set(currentIndex, temp);
93+
currentIndex = maxIndex;
94+
}
95+
else
96+
break; // The tree is a heap
97+
}
98+
99+
return removedObject;
100+
}
101+
102+
/** Remove the root from the heap */
103+
public E remove(Comparator<? super E> comparator) {
104+
if (list.size() == 0) return null;
105+
106+
E removedObject = list.get(0);
107+
list.set(0, list.get(list.size() - 1));
108+
list.remove(list.size() - 1);
109+
110+
int currentIndex = 0;
111+
while (currentIndex < list.size()) {
112+
int leftChildIndex = 2 * currentIndex + 1;
113+
int rightChildIndex = 2 * currentIndex + 2;
114+
115+
// Find the maximum between two children
116+
if (leftChildIndex >= list.size()) break; // The tree is a heap
117+
int maxIndex = leftChildIndex;
118+
if (rightChildIndex < list.size()) {
119+
if (comparator.compare(list.get(maxIndex),
120+
list.get(rightChildIndex)) < 0) {
121+
maxIndex = rightChildIndex;
122+
}
123+
}
124+
125+
// Swap if the current node is less than the maximum
126+
if (comparator.compare(list.get(currentIndex),
127+
list.get(maxIndex)) < 0) {
128+
E temp = list.get(maxIndex);
129+
list.set(maxIndex, list.get(currentIndex));
130+
list.set(currentIndex, temp);
131+
currentIndex = maxIndex;
132+
}
133+
else
134+
break; // The tree is a heap
135+
}
136+
137+
return removedObject;
138+
}
139+
140+
/** Get the number of nodes in the tree */
141+
public int getSize() {
142+
return list.size();
143+
}
144+
}
1.2 KB
Binary file not shown.
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
publicclassCircle
2+
extendsGeometricObject {
3+
privatedoubleradius;
4+
5+
publicCircle() {
6+
}
7+
8+
publicCircle(doubleradius) {
9+
this.radius =radius;
10+
}
11+
12+
publicCircle(doubleradius,
13+
Stringcolor,booleanfilled) {
14+
this.radius =radius;
15+
setColor(color);
16+
setFilled(filled);
17+
}
18+
19+
/** Return radius */
20+
publicdoublegetRadius() {
21+
returnradius;
22+
}
23+
24+
/** Set a new radius */
25+
publicvoidsetRadius(doubleradius) {
26+
this.radius =radius;
27+
}
28+
29+
@Override/** Return area */
30+
publicdoublegetArea() {
31+
returnradius *radius *Math.PI;
32+
}
33+
34+
/** Return diameter */
35+
publicdoublegetDiameter() {
36+
return2 *radius;
37+
}
38+
39+
@Override/** Return perimeter */
40+
publicdoublegetPerimeter() {
41+
return2 *radius *Math.PI;
42+
}
43+
44+
@Override/** Override the toString method in the Object class */
45+
publicStringtoString() {
46+
returnsuper.toString() +", Circle, Created: "
47+
+getDateCreated() +", Radius: " +radius;
48+
}
49+
}
3.02 KB
Binary file not shown.
Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
/*********************************************************************************
2+
* (Generic heap sort) Write the following two generic methods using heap sort. *
3+
* The first method sorts the elements using the Comparable interface and the *
4+
* second uses the Comparator interface. *
5+
* *
6+
* public static <E extends Comparable<E>> *
7+
* void heapSort(E[] list) *
8+
* public static <E> void heapSort(E[] list, *
9+
* Comparator<? super E> comparator) *
10+
*********************************************************************************/
11+
importjava.util.Comparator;
12+
13+
publicclassExercise_23_05 {
14+
15+
publicstatic <EextendsComparable<E>>voidheapSort(E[]list) {
16+
// Create a Heap
17+
Heap<E>heap =newHeap<>();
18+
19+
// Add elements to the heap
20+
for (inti =0;i <list.length;i++)
21+
heap.add(list[i]);
22+
23+
// Remove elements form the heap
24+
for (inti =list.length -1;i >=0;i--)
25+
list[i] =heap.remove();
26+
}
27+
28+
publicstatic <E>voidheapSort(E[]list,Comparator<?superE>comparator) {
29+
// Create a Heap
30+
HeapA<E>heap =newHeapA<>(comparator);
31+
32+
// Add elements to the heap
33+
for (inti =0;i <list.length;i++)
34+
heap.add(list[i]);
35+
36+
// Remove elements from the heap
37+
for (inti =list.length -1;i >=0;i--)
38+
list[i] =heap.remove();
39+
}
40+
41+
/** A test method */
42+
publicstaticvoidmain(String[]args) {
43+
/** Create an Array of Integers */
44+
Integer[]intArray = {-44, -5, -3,3,3,1, -4,0,1,2,4,5,53};
45+
46+
/** Create an Array of Doubles */
47+
Double[]doubleArray = {3.4,1.3, -22.1,14.8,6.0,2.3,12.2};
48+
49+
/** Create an Array of Characters */
50+
Character[]charArray = {'a','J','r'};
51+
52+
/** Create an Array of String */
53+
String[]stringArray = {"Tom","Susan","Kim"};
54+
55+
/** Heapsort the arrays */
56+
heapSort(intArray);
57+
heapSort(doubleArray);
58+
heapSort(charArray);
59+
heapSort(stringArray);
60+
61+
/** Display the array */
62+
System.out.print("Sorted Integers: ");
63+
printList(intArray);
64+
65+
System.out.print("Sorted Doubles: ");
66+
printList(doubleArray);
67+
68+
System.out.print("Sorted Characters: ");
69+
printList(charArray);
70+
71+
System.out.print("Sorted Strings: ");
72+
printList(stringArray);
73+
74+
// Create an array of 10 GeometricObjects
75+
GeometricObject[]list = {newCircle(5),newRectangle(4,5),
76+
newCircle(5.5),newRectangle(2.4,5),newCircle(0.5),
77+
newRectangle(4,65),newCircle(4.5),newRectangle(4.4,1),
78+
newCircle(6.5),newRectangle(4,5)};
79+
heapSort(list,newGeometricObjectComparator());
80+
System.out.print("Sorted elements: ");
81+
for (GeometricObjecte:list) {
82+
System.out.printf("%.2f ",e.getArea());
83+
}
84+
System.out.println();
85+
}
86+
87+
/** Display elements in an Array */
88+
publicstaticvoidprintList(Object[]list) {
89+
for (inti =0;i <list.length;i++)
90+
System.out.print(list[i] +" ");
91+
System.out.println();
92+
}
93+
}
1.25 KB
Binary file not shown.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp