I'm having trouble with a Heapsort code in java.
I'd like it to print out the given list as a max heap as as soon as has been built. so far so good.
What I'm struggling with is the sorting part. I'd like the heapSort() method to print out the given array each step of the sorting process when the largest Element of the heap is taken out and inserted at the last position of the array. for some reason it kind of works up to some point but after 3 times it throws out something that shouldn't be and the end result is not the correct one.
I'd really appreciate any kind of constructive criticism and help. I apologize in advance for my code style, I'm pretty new to java and I really tried my best.
here's the output:
Max-Heap:
[26, 22, 18, 14, 12, 16, 8, 6, 10, 4]
sorting process:
[22, 14, 18, 10, 12, 16, 8, 6, 4, 26]
[18, 14, 16, 10, 12, 4, 8, 6, 22, 26]
[16, 14, 8, 10, 12, 4, 6, 18, 22, 26]
[14, 12, 8, 10, 26, 4, 16, 18, 22, 6]
[12, 26, 8, 10, 6, 14, 16, 18, 22, 4]
[26, 12, 8, 10, 6, 14, 16, 18, 22, 4]
[12, 26, 8, 22, 6, 14, 16, 18, 10, 4]
[26, 22, 12, 18, 6, 14, 16, 8, 10, 4]
[26, 22, 12, 18, 6, 14, 16, 8, 10, 4]
And the code:
public static void max_Heapify(int []a, int i){
int left=2*i+1;
int right= 2*i+2;
int largest;
int heapSize= a.length;
if(left<heapSize && a[left]>a[i]){
largest= left;
}else{
largest= i;
}
if(right<heapSize && a[right]>a[largest]){
largest = right;
}
if(largest != i){
swap(a,i,largest);
max_Heapify(a, largest);
}
}
public static void createMax_Heap(int []a){
int heapSize= a.length;
for(int i=heapSize/2; i>=0; i--){
max_Heapify(a, i);
}
System.out.println("Max-Heap: " +"\n"+Arrays.toString(a));
}
public static void heapSort(int []a){
createMax_Heap(a);
System.out.println("sorting process: ");
for(int i=a.length-1; i>=1; i--){
swap(a,0,i);
int heapSize= a.length-1;
max_Heapify(a, 0);
System.out.println(Arrays.toString(a));
}
}
public static void swap(int[] a, int i, int j)
{
int tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public static void main(String[] args){
int myArr[]={10,4,8,6,26,16,18,22,14,12};
heapSort(myArr);
}
When you are ordering, you are always considering that the vector is full. Ordering after you build a heap is, conceptually, removing every highest member of the heap (which is on top by heap definition), and then rearraging the heap. Since you obviously can't remove an element of an array, you should "fake" it by having a variable with the last index you should consider.
In more technical terms, your max_Heapify function should:
int lastIndex, referring to you highest index (and thus being called for the first time with array.length-1.0) and the lastIndex.Hope that helps.