HeapSort Fehler

[deiwid]

Hallo, hab einen Heap Sort in eclipse programmiert. Wenn kommen in einigen Zeilen Fehlermeldungen, wo ich aber nicht weiß was falsch ist. Kann mir da bitte jemand helfen.

import java.util.Arrays;

public class Heap {
	
	private int[] a;
	private int heap_size;
	
	public void Heapsort(int a[]) {
		
        this.a=a;
		maximumHeap(); //Fehlermeldung
		
			for(int i = a.length-1; i>=2; i-- ){
				int tmp = a[1];
				a[1] = a[i];
				a[i] = tmp;
				heap_size--;
				max_heap(a, 1);
			}
	}
	
	
	public void maximumHeap() {
		heap_size = a.length-1;
		
		for(int i = (a.length-1)/2; i>=1; i--){
			max_heap(a, i);                             // Fehlermeldung
		}	
	}
	
	
	public void max_heap(int[] a ,int i) {
		
		int l = 2*i;
		int r = 2*i+1;
		int largest;
		
		if(l>=heap_size && (a[l] > a[i])) {
			largest = l ; }
		else {
			largest = i; }
		
		if(r>=heap_size && (a[r] > a[largest])) {  //Fehlermeldung
			largest = r; }
		
		if(largest!=i) {
			int temp = a[i];
			a[i] = a[largest];
			a[largest]=temp;
			max_heap(a, largest);
		}	
	}
	
		
    public String toString() {
        return Arrays.toString(a); //gibt Array aus
    }

}

public class Test {

	public static void main ( String[] args){
		
		Heap s = new Heap();
		s.Heapsort(new int[] {12, 56, 4 ,34, 89, 1, 2}); //Fehlermeldung
		s.toString();
	}
}

Das kommt als Fehlermeldung: Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 7
at Heap.max_heap(Heap.java:43)
at Heap.maximumHeap(Heap.java:27)
at Heap.Heapsort(Heap.java:11)
at Test.main(Test.java:7)

Bitte um Lösungshilfe! Danke!

 

[Marco13]

Der Array hat eine Länge von 7, also Indizes 0-6

Aufrufkette:

s.Heapsort(new int[] {12, 56, 4 ,34, 89, 1, 2}); //Fehlermeldung
..
maximumHeap(); //Fehlermeldung
...
for(int i = (a.length-1)/2; i>=1; i--){ [b]// Hier ist i am Anfang (7-1)/2=3[/b]
    max_heap(a, i);                             // Fehlermeldung
}   
...

// In max_heap:
int r = 2*i+1; [b]// Hier ist r am Anfang 2*3+1=7 (wenn i=3 ist) 
if(r>=heap_size && (a[r] > a[largest])) {  //Fehlermeldung [b] Weil auf index 7 zugegriffen wird[/b]

Reicht das als "Lösungshilfe"? Oder wolltest du direkt DIE Lösung? (Da muss man immer so lange nachdenken )

 

[deiwid]

also muss ich ich einfach schreiben: int r = 2*i; ohne +1 ?

 

[Marco13]

Das würde zwar den Fehler verhindern, aber ob der Algorithmus mit dieser Änderung noch so funktioniert, wie er sollte, kann man auf die Schnelle und nur durch drüberschauen nicht sagen - das muss derjenige, der den Algorithmus implementiert hat, wissen oder sich erarbeiten...