Skip to content

Commit 756ca76

Browse files
author
cfdcoder
committed
complete max heap sort
1 parent 9abc846 commit 756ca76

File tree

55 files changed

+5208
-1599
lines changed

Some content is hidden

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

55 files changed

+5208
-1599
lines changed

‎.metadata/.plugins/org.eclipse.core.resources/.history/0/b0a70d239aaf001517cea66f72e0b330

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

‎.metadata/.plugins/org.eclipse.core.resources/.history/18/00ccd5918faf001517cea66f72e0b330

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package study;
2+
3+
public class HeapSort {
4+
int[] Arr;
5+
6+
private void BuildMaxHeap(int[] A){
7+
8+
}
9+
10+
private void BuildMinHeap(int[] A){
11+
12+
}
13+
14+
private void MinHepify(){
15+
16+
}
17+
18+
private void MaxHepify(int[] A, int index){
19+
20+
}
21+
22+
private void DeleteRoot(){
23+
24+
}
25+
26+
private int GetParentIndex(int index){
27+
return (index/2);
28+
}
29+
30+
private int GetLeftChildIndex(int index){
31+
return (index*2);
32+
}
33+
34+
private int GetRightChildIndex(int index){
35+
return (index*2+1);
36+
}
37+
public static void main(String[] args) {
38+
// TODO Auto-generated method stub
39+
40+
}
41+
42+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/1d/60ecc60096af001517cea66f72e0b330

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
package study;
2+
3+
public class HeapSort {
4+
int[] Arr;
5+
int heapSize;
6+
HeapSort(int[] A){
7+
this.Arr=A.clone();
8+
this.heapSize=A.length;
9+
}
10+
11+
public void HeapMaxSort(int[] A){
12+
BuildMaxHeap(A);
13+
for(int i=A.length-1;i>1;i--){
14+
Exchange(A, 1, i);
15+
this.heapSize--;
16+
MaxHeapify(A, 1);
17+
}
18+
}
19+
20+
private void BuildMaxHeap(int[] A){
21+
for (int i=this.heapSize/2;i>0;i--){
22+
MaxHeapify(A, i);
23+
}
24+
}
25+
26+
private void BuildMinHeap(int[] A){
27+
28+
}
29+
30+
private void MinHeapify(){
31+
32+
}
33+
34+
private void MaxHeapify(int[] A, int index){
35+
int largest;
36+
int left=GetLeftChildIndex(index);
37+
int right=GetRightChildIndex(index);
38+
if(left<=this.heapSize && A[left-1]>A[index-1])
39+
largest=left;
40+
else
41+
largest=index;
42+
43+
if(right<=this.heapSize && A[right-1]>A[largest-1])
44+
largest=right;
45+
46+
if(largest!=index){
47+
Exchange(A, index-1, largest-1);
48+
MaxHeapify(A, largest);
49+
}
50+
}
51+
52+
private void Exchange(int[] A, int x, int y){
53+
int temp=A[x];
54+
A[x]=A[y];
55+
A[y]=A[x];
56+
}
57+
58+
private void DeleteRoot(){
59+
60+
}
61+
62+
private int GetParentIndex(int index){
63+
return (index/2);
64+
}
65+
66+
private int GetLeftChildIndex(int index){
67+
return (index*2);
68+
}
69+
70+
private int GetRightChildIndex(int index){
71+
return (index*2+1);
72+
}
73+
74+
public void OutputArray(int A[]) {
75+
for (int i = 0; i < A.length; i++) {
76+
System.out.print(A[i] + ", ");
77+
}
78+
System.out.println(" ");
79+
}
80+
81+
public static void main(String[] args) {
82+
// TODO Auto-generated method stub
83+
int[] Array = { 7, 1, 9, 5, 0, 3};
84+
HeapSort HS=new HeapSort(Array);
85+
System.out.println("Unsorted Array:");
86+
HS.OutputArray(HS.Arr);
87+
HS.BuildMaxHeap(HS.Arr);
88+
System.out.println("Sorted Array:");
89+
HS.OutputArray(HS.Arr);
90+
91+
}
92+
93+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/2/0011af8294af001517cea66f72e0b330

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
package study;
2+
3+
public class HeapSort {
4+
int[] Arr;
5+
HeapSort(int[] A){
6+
this.Arr=A.clone();
7+
}
8+
9+
public void HeapMaxSort(int[] A){
10+
int heapSize=A.length;
11+
BuildMaxHeap(A);
12+
for(int i=A.length;i>1;i--){
13+
Exchange(A, 1, i);
14+
heapSize--;
15+
MaxHeapify(A, 1);
16+
}
17+
}
18+
private void BuildMaxHeap(int[] A){
19+
int heapSize=A.length;
20+
for (int i=heapSize/2;i>0;i--){
21+
MaxHeapify(A, i);
22+
}
23+
}
24+
25+
private void BuildMinHeap(int[] A){
26+
27+
}
28+
29+
private void MinHeapify(){
30+
31+
}
32+
33+
private void MaxHeapify(int[] A, int index){
34+
int largest;
35+
int left=GetLeftChildIndex(index);
36+
int right=GetRightChildIndex(index);
37+
if(left<=A.length && A[left-1]>A[index-1])
38+
largest=left;
39+
else
40+
largest=index;
41+
42+
if(right<=A.length && A[right-1]>A[largest-1])
43+
largest=right;
44+
45+
if(largest!=index){
46+
Exchange(A, index, largest);
47+
MaxHeapify(A, largest);
48+
}
49+
}
50+
51+
private void Exchange(int[] A, int x, int y){
52+
int temp=A[x];
53+
A[x]=A[y];
54+
A[y]=A[x];
55+
}
56+
57+
private void DeleteRoot(){
58+
59+
}
60+
61+
private int GetParentIndex(int index){
62+
return (index/2);
63+
}
64+
65+
private int GetLeftChildIndex(int index){
66+
return (index*2);
67+
}
68+
69+
private int GetRightChildIndex(int index){
70+
return (index*2+1);
71+
}
72+
73+
public void OutputArray(int A[]) {
74+
for (int i = 0; i < A.length; i++) {
75+
System.out.print(A[i] + ", ");
76+
}
77+
System.out.println(" ");
78+
}
79+
80+
public static void main(String[] args) {
81+
// TODO Auto-generated method stub
82+
int[] Array = { 0, 1, 3, 5, 7, 9};
83+
HeapSort HS=new HeapSort(Array);
84+
HS.OutputArray(HS.Arr);
85+
HS.HeapMaxSort(HS.Arr);
86+
87+
}
88+
89+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/31/b005bdd291af001517cea66f72e0b330

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

0 commit comments

Comments
 (0)