Skip to content

Commit 4d712c7

Browse files
author
cfdcoder
committed
update HeapSort.java
1 parent 756ca76 commit 4d712c7

File tree

65 files changed

+4796
-1654
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

65 files changed

+4796
-1654
lines changed

‎.metadata/.log

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,3 +26,17 @@ user global configuration and to define the default location to store repositori
2626
not correct please set the HOME environment variable and restart Eclipse. Otherwise Git for Windows and
2727
EGit might behave differently since they see different configuration options.
2828
This warning can be switched off on the Team > Git > Confirmations and Warnings preference page.
29+
!SESSION 2015-12-31 12:02:12.993 -----------------------------------------------
30+
eclipse.buildId=4.5.1.M20150904-0015
31+
java.version=1.8.0_65
32+
java.vendor=Oracle Corporation
33+
BootLoader constants: OS=win32, ARCH=x86_64, WS=win32, NL=en_US
34+
Framework arguments: -product org.eclipse.epp.package.java.product
35+
Command-line arguments: -os win32 -ws win32 -arch x86_64 -product org.eclipse.epp.package.java.product
36+
37+
!ENTRY org.eclipse.egit.ui 2 0 2015-12-31 12:02:32.271
38+
!MESSAGE Warning: The environment variable HOME is not set. The following directory will be used to store the Git
39+
user global configuration and to define the default location to store repositories: 'C:\Users\cfdcoder'. If this is
40+
not correct please set the HOME environment variable and restart Eclipse. Otherwise Git for Windows and
41+
EGit might behave differently since they see different configuration options.
42+
This warning can be switched off on the Team > Git > Confirmations and Warnings preference page.

‎.metadata/.plugins/org.eclipse.core.resources/.history/0/00ea169ae6af001517cea66f72e0b330

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

‎.metadata/.plugins/org.eclipse.core.resources/.history/0/10e6739ee7af001517cea66f72e0b330

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

‎.metadata/.plugins/org.eclipse.core.resources/.history/10/b024e194e6af001517cea66f72e0b330

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

‎.metadata/.plugins/org.eclipse.core.resources/.history/12/808608489eaf001517cea66f72e0b330

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

0 commit comments

Comments
 (0)