Heap

H

HansPeterLoft

Gast
Hallo,
ich versuche einen Heap zu implementieren, die insert() Funktion funktioniert,
jedoch getMin() gibt einen ArrayIndexOutOfBOundException.
Ich verstehe aber einfach nicht was daran falsch ist:

Java:
import java.util.*;

public class HeapSort {
	
	void insert(int x, int [] list, int size) {        //falls k-1 statt k/2 -> insertion Sort
		int k = size + 1;                              //1 wegen getMin(), sonst wäre 2+k nicht möglich
		while (x <= list[k/2] && k>1) {
			list[k] = list[k/2];
			k = k/2;
		} list[k] = x;
	}
	
	int getMin(int [] list) {
		int returnValue = list[1];
		int size = list.length;
		int k = 1;
		list[k] = list[size-1];
		int w = list[1];
		
		
		while(list[2*k] < list[k] || list [2*k + 1] < list[k]) {
			boolean b = (list[2*k] > list[2*k + 1]);
			if(b) {
				list[k] = list[2*k + 1];
				list[2*k + 1] = w;
				k= k*2 + 1;
			} else {
				list[k] = list[2*k];
				list[2*k] = w;
				k = k*2;
			}
		} 
		return returnValue;
	}
}

Zur Theorie:
Man nimmt den letzen Knoten des untersten Niveaus und ersetzt damit die Wurzel.
Dann schaut man ob einer der zwei Nachkommen kleiner als der Knoten ist:
Knoten k, Nachkommen 2k, 2k+1; Falls Ja -> kleineren vertauschen.
 
Zuletzt bearbeitet von einem Moderator:
N

nillehammer

Gast
list.length = 0 oder 1: Bereits in der ersten Zeile der Methode geht der Index über die erlaubten Grenzen hinaus
Ansonsten diese ganzen
Code:
*2
. Da bist Du ganz schnell übers Ziel (den höchst möglichen Index, also length -1) hinaus geschossen.
 
H

HansPeterLoft

Gast
Ok, ja da könnte man noch eine if-Anweisung machen, wenn die list.length < 2 ist.
Wie aber kann ich es sonst machen? Der nächste Wert liegt ja bei list[2*k] oder list [2*k + 1]?
Gruss Peter
 
H

HansPeterLoft

Gast
So, ich habe jetzt folgendes:
Java:
int getMin(int [] list) {
		int returnValue = list[1];
		int size = list.length;
		int k = 1;
		list[k] = list[size-1];
		int w = list[1];
			
		while(k < size/2) {
			int j = 2*k;
			if(j < size && list[j] > list[j+1])
				j++;
			if(w <= list[j]) break;
			list[k] = list[j];
			k = j;
		} list[k] = w;
		return returnValue;
}

Was eigentlich stimmen muss, aber das Problem ist, dass wenn ich ein
Knoten lösche, der gar nicht richtig im Array gelöscht wird, Der Knoten wird einfach
durch eine Zahl ersetzt, die grösse bleibt gleich. Ich denke wenn ich jetzt dynamische Arrays machen ist das ganze schon viel weniger effizient, wie kann ich sonst einen Eintrag löschen?
Gruss
 
H

HansPeterLoft

Gast
Ah, ich habe es ziemlich simple hinbekommen, mit dem Aufruf:
Java:
public static void main(String [] args) {
		int size = 11;
		int [] list = new int[size];
		Random ran = new Random();
		HeapSort h = new HeapSort();

		for(int i = 0; i<size- 1; i++ ) 
			h.insert(ran.nextInt(20) + 1, list, i);
		out(list);
		for(int i = 0; i<size -1; i++)
			System.out.print(h.getMin(list,list.length-i) + " ");
	}
	
	static void out(int [] x) {
		for(int i = 0;i<x.length;i++) {
			System.out.print(x[i] + " ");
		}
		System.out.println();
	}
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
V Ist Off-Heap-Speicher dasselbe wie Stack-Speicher? Java Basics - Anfänger-Themen 2
S Java Client-je nach Heap Size Größe startet Applikation oder nicht Java Basics - Anfänger-Themen 4
KogoroMori21 Stack und Heap Speicher Java Basics - Anfänger-Themen 1
G Min und Max heap Java Basics - Anfänger-Themen 1
M Java heap space Fehlermeldung beheben Java Basics - Anfänger-Themen 3
F speicherort stack oder heap Java Basics - Anfänger-Themen 1
M Algorithmus Max-Heap? Java Basics - Anfänger-Themen 3
P Stack, Heap Java Basics - Anfänger-Themen 13
G Heap Space erhöhen (64bit) Java Basics - Anfänger-Themen 45
S Java memory fehler: Exception in thread "AWT-EventQueue-0" java.lang.OutOfMemoryError: Java heap spa Java Basics - Anfänger-Themen 5
A Heap Space Error bei rekursiver Suche in Dateien trotz nur einer Zeile im Speicher Java Basics - Anfänger-Themen 26
J Array von Objekten, wie schauts im Heap / Stack aus ? Java Basics - Anfänger-Themen 7
V Heap-Sort Java Basics - Anfänger-Themen 0
M Frage zu Stack und Heap Java Basics - Anfänger-Themen 1
H Heap-Auslasung verdoppelt sich schlagartig Java Basics - Anfänger-Themen 3
M Java Arbeitsspeicherverbrauch, Heap Space error korrigieren? Java Basics - Anfänger-Themen 18
D Java Heap Space Probleme Java Basics - Anfänger-Themen 7
B Stack/Heap Frage Java Basics - Anfänger-Themen 36
C Warning: Type safety: Potential heap pollution via varargs parameter array Java Basics - Anfänger-Themen 5
S Input/Output Java heap space Java Basics - Anfänger-Themen 8
W Compiler-Fehler "Could not reserve enough space for object heap"... und dann raucht das Programm ab Java Basics - Anfänger-Themen 3
B OOP Zwei gleichnamige Objekte auf dem heap Java Basics - Anfänger-Themen 4
H Heap Java Basics - Anfänger-Themen 2
A Java heap space Java Basics - Anfänger-Themen 11
T Out of Memory (Java Heap Space) Java Basics - Anfänger-Themen 9
B Heap-Speicher wieder freigeben Java Basics - Anfänger-Themen 10
D java heap space Java Basics - Anfänger-Themen 6
S Java Heap space trotz -Xmx1024 Java Basics - Anfänger-Themen 10
N Heap Dump Java Basics - Anfänger-Themen 23
C 'OutOfMemoryError: Java heap space' Java Basics - Anfänger-Themen 5
E ternärer Heap in Array-Form Java Basics - Anfänger-Themen 6
L heap space, LinkedList umspeichern Java Basics - Anfänger-Themen 15
E begrenzung des platzes im heap Java Basics - Anfänger-Themen 4
D java.lang.outofmemoryerror java heap space bei Hashtable Java Basics - Anfänger-Themen 3
G Frage zur Heap-Belegung Java Basics - Anfänger-Themen 2
neurox java.lang.OutOfMemoryError: Java heap space Java Basics - Anfänger-Themen 18
B java.lang.OutOfMemoryError: Java heap space bei Musikplayer Java Basics - Anfänger-Themen 7
M Java Heap Space durch Übergang von einer Klasse in die ander Java Basics - Anfänger-Themen 3
N Applet Heap vergrößern Java Basics - Anfänger-Themen 10
G warum heap space problem? Java Basics - Anfänger-Themen 6
G heap size vergrößern Java Basics - Anfänger-Themen 6
S memory heap problem Java Basics - Anfänger-Themen 9
V warum heap space überlastung Java Basics - Anfänger-Themen 2
G error wegen heap space Java Basics - Anfänger-Themen 4
M Beadarf ermitteln für Java heap space Java Basics - Anfänger-Themen 4
M Dateien lesen/schreiben und Heap Space Probleme Java Basics - Anfänger-Themen 8
G Aktuelle Heap-Größe auslesen? Java Basics - Anfänger-Themen 3
G Aus Array einen Heap erstellen Java Basics - Anfänger-Themen 5
D suchbaum out of heap space Java Basics - Anfänger-Themen 8
D Heap erweitern Java Basics - Anfänger-Themen 3
R Java heap space Java Basics - Anfänger-Themen 4
E Heap Size einstellen Java Basics - Anfänger-Themen 7
S OutOfMemoryError: Java heap space Java Basics - Anfänger-Themen 6
J Morgen Java-Klausur. Stack, Heap, Method-Area Java Basics - Anfänger-Themen 2
M Java Heap Space während der Laufzeit ändern Java Basics - Anfänger-Themen 2
E fehlermeldung "java heap space" Java Basics - Anfänger-Themen 21
E wieviele objekte am heap?? Java Basics - Anfänger-Themen 14

Ähnliche Java Themen

Neue Themen


Oben