Skip to content

Commit 444f4d8

Browse files
author
cfdcoder
committed
Delete the HeapSort.java, and modify the HeapSort2.java
1 parent 4d712c7 commit 444f4d8

37 files changed

+3658
-1592
lines changed

‎.metadata/.plugins/org.eclipse.core.resources/.history/43/503b9eea0db000151d15c07ec223227e

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
package study;
2+
/**
3+
* this version make the heap index and array index consistent, namely both begin from 0
4+
* */
5+
6+
public class HeapSort2 {
7+
int[] Arr;
8+
9+
HeapSort2(int[] A){
10+
this.Arr=A.clone();
11+
}
12+
13+
//heap index start from 0, so if the parentIndex is i, the leftIndex is 2*i+1, and rightIndex is 2*i+2,
14+
private static int left(int i){
15+
return 2*i + 1;
16+
}
17+
18+
private static int right(int i){
19+
return 2*i + 2;
20+
}
21+
22+
public static void maxHeapify(int[] data, int i, int heapSize){
23+
24+
int l = left(i);
25+
int r = right(i);
26+
int largest;
27+
28+
if(l < heapSize && data[l] > data[i]){
29+
largest = l;
30+
}else{
31+
largest = i;
32+
}
33+
34+
if(r < heapSize && data[r] > data[largest]){
35+
largest = r;
36+
}
37+
38+
if(largest != i){
39+
swap(data,i,largest);
40+
maxHeapify(data, largest, heapSize);
41+
}
42+
}
43+
44+
public static void buildMaxHeap(int[] data){
45+
int heapSize = data.length;
46+
47+
for(int i = heapSize/2; i >=0; i--){
48+
maxHeapify(data, i, heapSize);
49+
}
50+
}
51+
52+
public static void heapSort(int[] data){
53+
int heapSize = data.length;
54+
55+
buildMaxHeap(data);
56+
System.out.println("Max heap built is:");
57+
outputArray(data);//check if the heap is correct
58+
for(int i = heapSize - 1; i > 0; i--){
59+
swap(data,0,i);//equivalent to swap(heapData,1,i);
60+
heapSize = heapSize - 1;
61+
maxHeapify(data, 0, heapSize);//equivalent to maxHeapify(heapData, 1, heapSize);
62+
}
63+
}
64+
65+
public static void swap(int[] data, int i, int j) {
66+
int temp = data[i];
67+
data[i] = data[j];
68+
data[j] = temp;
69+
}
70+
71+
public static void outputArray(int A[]) {
72+
for (int i = 0; i < A.length; i++) {
73+
System.out.print(A[i] + ", ");
74+
}
75+
System.out.println(" ");
76+
}
77+
78+
79+
public static void main(String[] args) {
80+
// TODO Auto-generated method stub
81+
int[] Array = { 7,3,7,9,5,2,11,5};
82+
HeapSort HS=new HeapSort(Array);
83+
HS.heapSort(HS.Arr);
84+
HS.outputArray(HS.Arr);
85+
}
86+
87+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/56/d031bf3d0ab000151d15c07ec223227e

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package study;
2+
3+
public class HeapSort2 {
4+
int[] Arr;
5+
6+
HeapSort(int[] A){
7+
this.Arr=A.clone();
8+
}
9+
10+
//heap index start from 1, so if the parentIndex is i, the leftIndex is 2*i, and rightIndex is 2*i+1,
11+
private static int left(int i){
12+
return 2*i;
13+
}
14+
15+
private static int right(int i){
16+
return 2*i + 1;
17+
}
18+
19+
public static void maxHeapify(int[] data, int i, int heapSize){
20+
21+
int l = left(i);
22+
int r = right(i);
23+
int largest;
24+
25+
if(l < heapSize && data[l] > data[i]){
26+
largest = l;
27+
}else{
28+
largest = i;
29+
}
30+
31+
if(r < heapSize && data[r] > data[largest]){
32+
largest = r;
33+
}
34+
35+
if(largest != i){
36+
swap(data,i,largest);
37+
maxHeapify(data, largest, heapSize);
38+
}
39+
}
40+
41+
public static void buildMaxHeap(int[] data){
42+
int heapSize = data.length;
43+
44+
for(int i = heapSize/2; i >=0; i--){
45+
maxHeapify(data, i, heapSize);
46+
}
47+
}
48+
49+
public static void heapSort(int[] data){
50+
int heapSize = data.length;
51+
52+
buildMaxHeap(data);
53+
System.out.println("Max heap built is:");
54+
outputArray(data);//check if the heap is correct
55+
for(int i = heapSize - 1; i > 0; i--){
56+
swap(data,0,i);//equivalent to swap(heapData,1,i);
57+
heapSize = heapSize - 1;
58+
maxHeapify(data, 0, heapSize);//equivalent to maxHeapify(heapData, 1, heapSize);
59+
}
60+
}
61+
62+
public static void swap(int[] data, int i, int j) {
63+
int temp = data[i];
64+
data[i] = data[j];
65+
data[j] = temp;
66+
}
67+
68+
public static void outputArray(int A[]) {
69+
for (int i = 0; i < A.length; i++) {
70+
System.out.print(A[i] + ", ");
71+
}
72+
System.out.println(" ");
73+
}
74+
75+
76+
public static void main(String[] args) {
77+
// TODO Auto-generated method stub
78+
int[] Array = { 7,3,7,9,5,2,5};
79+
HeapSort HS=new HeapSort(Array);
80+
HS.heapSort(HS.Arr);
81+
HS.outputArray(HS.Arr);
82+
}
83+
84+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/6d/80f79be60eb000151d15c07ec223227e

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
package study;
2+
/**
3+
* this version make the heap index and array index consistent, namely both begin from 0
4+
* */
5+
6+
public class HeapSort2 {
7+
int[] Arr;
8+
9+
HeapSort2(int[] A){
10+
this.Arr=A.clone();
11+
}
12+
13+
//heap index start from 0, so if the parentIndex is i, the leftIndex is 2*i+1, and rightIndex is 2*i+2,
14+
private static int left(int i){
15+
return 2*i + 1;
16+
}
17+
18+
private static int right(int i){
19+
return 2*i + 2;
20+
}
21+
22+
public static void maxHeapify(int[] data, int i, int heapSize){
23+
24+
int l = left(i);
25+
int r = right(i);
26+
int largest;
27+
28+
if(l < heapSize && data[l] > data[i]){
29+
largest = l;
30+
}else{
31+
largest = i;
32+
}
33+
34+
if(r < heapSize && data[r] > data[largest]){
35+
largest = r;
36+
}
37+
38+
if(largest != i){
39+
swap(data,i,largest);
40+
maxHeapify(data, largest, heapSize);
41+
}
42+
}
43+
44+
public static void buildMaxHeap(int[] data){
45+
int heapSize = data.length;
46+
47+
for(int i = heapSize/2-1; i >=0; i--){
48+
maxHeapify(data, i, heapSize);
49+
}
50+
}
51+
52+
public static void heapSort(int[] data){
53+
int heapSize = data.length;
54+
55+
buildMaxHeap(data);
56+
System.out.println("Max heap built is:");
57+
outputArray(data);//check if the heap is correct
58+
for(int i = heapSize - 1; i >=0; i--){
59+
swap(data,0,i);//equivalent to swap(heapData,1,i);
60+
heapSize = heapSize - 1;
61+
maxHeapify(data, 0, heapSize);//equivalent to maxHeapify(heapData, 1, heapSize);
62+
}
63+
}
64+
65+
public static void swap(int[] data, int i, int j) {
66+
int temp = data[i];
67+
data[i] = data[j];
68+
data[j] = temp;
69+
}
70+
71+
public static void outputArray(int A[]) {
72+
for (int i = 0; i < A.length; i++) {
73+
System.out.print(A[i] + ", ");
74+
}
75+
System.out.println(" ");
76+
}
77+
78+
79+
public static void main(String[] args) {
80+
// TODO Auto-generated method stub
81+
int[] Array = { 7,3,9,6,2,11,5};
82+
HeapSort HS=new HeapSort(Array);
83+
HS.heapSort(HS.Arr);
84+
HS.outputArray(HS.Arr);
85+
}
86+
87+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/6d/c0b28fcf0eb000151d15c07ec223227e

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
package study;
2+
/**
3+
* this version make the heap index and array index consistent, namely both begin from 0
4+
* */
5+
6+
public class HeapSort2 {
7+
int[] Arr;
8+
9+
HeapSort2(int[] A){
10+
this.Arr=A.clone();
11+
}
12+
13+
//heap index start from 0, so if the parentIndex is i, the leftIndex is 2*i+1, and rightIndex is 2*i+2,
14+
private static int left(int i){
15+
return 2*i + 1;
16+
}
17+
18+
private static int right(int i){
19+
return 2*i + 2;
20+
}
21+
22+
public static void maxHeapify(int[] data, int i, int heapSize){
23+
24+
int l = left(i);
25+
int r = right(i);
26+
int largest;
27+
28+
if(l < heapSize && data[l] > data[i]){
29+
largest = l;
30+
}else{
31+
largest = i;
32+
}
33+
34+
if(r < heapSize && data[r] > data[largest]){
35+
largest = r;
36+
}
37+
38+
if(largest != i){
39+
swap(data,i,largest);
40+
maxHeapify(data, largest, heapSize);
41+
}
42+
}
43+
44+
public static void buildMaxHeap(int[] data){
45+
int heapSize = data.length;
46+
47+
for(int i = heapSize/2-1; i >=0; i--){
48+
maxHeapify(data, i, heapSize);
49+
}
50+
}
51+
52+
public static void heapSort(int[] data){
53+
int heapSize = data.length;
54+
55+
buildMaxHeap(data);
56+
System.out.println("Max heap built is:");
57+
outputArray(data);//check if the heap is correct
58+
for(int i = heapSize - 1; i > 0; i--){
59+
swap(data,0,i);//equivalent to swap(heapData,1,i);
60+
heapSize = heapSize - 1;
61+
maxHeapify(data, 0, heapSize);//equivalent to maxHeapify(heapData, 1, heapSize);
62+
}
63+
}
64+
65+
public static void swap(int[] data, int i, int j) {
66+
int temp = data[i];
67+
data[i] = data[j];
68+
data[j] = temp;
69+
}
70+
71+
public static void outputArray(int A[]) {
72+
for (int i = 0; i < A.length; i++) {
73+
System.out.print(A[i] + ", ");
74+
}
75+
System.out.println(" ");
76+
}
77+
78+
79+
public static void main(String[] args) {
80+
// TODO Auto-generated method stub
81+
int[] Array = { 7,3,9,6,2,11,5};
82+
HeapSort HS=new HeapSort(Array);
83+
HS.heapSort(HS.Arr);
84+
HS.outputArray(HS.Arr);
85+
}
86+
87+
}

0 commit comments

Comments
 (0)